백준 20035번 이동하기5

문제 설명

이번 문제는 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열부터 지나가는 경로 하나만 있으면 됩니다. 

예제 1

열에 해당한 B1이 아무리 다른 Bj에 비해 작더라도 Amax가 전체 사탕 개수에 미치는 영향이 가장 크므로 1열부터 Amax가 있는 행까지 내려가야 합니다.

 

Ai 중 가장 큰 값이 두 개 이상일 경우 첫 번째 Amax가 있는 행으로 이동, Bmax가 있는 열을 따라 이동, 그 다음 마지막 Amax가 있는 행에서 M열까지 이동한 뒤 (N,M)으로 이동합니다.

예제 2

위와 같이 이동하는 이유는, Amax행을 따라 최대한 많이 이동하고, Bmax열을 최대한 많이 지나가도록 하기 위해서 입니다.

 

사탕의 개수는 행의 사탕의 개수에 가장 큰 영향을 받으므로 행을 위주로 행동하되, 가장 많은 사탕이 있는 열 또한 최대한 많이 이동할 수 있도록 해줍니다.

 

 

풀이

Amax와 Bmax 찾기

행과 열의 사탕개수를 순회하면서 가장 큰 값이 있는 인덱스를 저장해줍니다.

 

Amax의 개수에 따른 이동 경로의 사탕 개수 최대값 구하기

Amax가 한 개일 경우 해당 행을 전부 지나가는 이동경로로 움직이도록 해줍니다.

Amax가 두 개 이상일 경우 첫 번째와 마지막 Amax 행을 지나갈 수 있도록, 또한 Bmax를 지나가도록 이동해줍니다.

(Bmax가 여러개인 경우 어떠한 Bmax가 있는 열로 이동하는지는 상관 없습니다.)

 

 

 

해결

이번 문제는 오른쪽 아래로만 이동한다는 규칙과, 사탕 개수를 최대로 하는 이동경로를 생각하면 풀 수 있었던 문제입니다.

 

문제 링크 : https://www.acmicpc.net/problem/20035

20035번: 이동하기 5

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/20035.py