반응형
SMALL
백준 20035 이동하기 5
-
백준 20035번 이동하기5알고리즘 2023. 3. 31. 11:11
문제 설명 이번 문제는 N*M크기의 미로가 주어지고 (i,j)에 Ai * 10^9 + Bj 개의 사탕이 놓여져 있을 때, (1,1)에서 출발하여 (N,M)으로 이동하면서 얻을 수 있는 사탕 개수의 최대값을 구하는 문제입니다. (r,c)에서 이동할 수 있는 칸은 (r+1,c), (r,c+1)입니다. 문제 풀이 아이디어 최대값을 갖는 방법 행과 열에 따라 사탕의 개수가 달라지게 됩니다. 그리고, 행에 의해 구해지는 사탕의 개수는 10^9를 곱하기 때문에 Ai(행의 사탕개수)가 큰 곳을 많이 지나다녀야 됩니다. 이동 방법 (가장 큰 Ai를 Amax, 가자 큰 Bi를 Bmax라 하겠습니다) Ai 중 가장 큰 값이 한 개일 경우 해당 행을 무조건 1열부터 지나가는 경로 하나만 있으면 됩니다. 열에 해당한 B1이 ..