로봇 청소기가 청소할 지역들을 표현한 n\times n 크기의 행렬 M… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 알고리즘] 26년 1회차
로봇 청소기가 청소할 지역들을 표현한 n×n 크기의 행렬 M이 있다. <보기>는 4 × 4 크기의 행렬 M에 대한 예시로, 행렬의 각 원소 Mi,j는 지역 (i,j)을 청소했을 때 얻을 수 있는 양의 정수인 청소 점수이다. 한편, 로봇 청소기는 오른쪽이나 아래쪽으로만 이동할 수 있으며, 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다. 로봇 청소기가 지역 (1, 1)에서 청소를 시작하여 지역 (n,n)에 도착할 때까지, 가장 많은 청소 점수를 얻고자 한다. 동적 프로그래밍(dynamic programming)을 이용하여 이 문제를 해결하기 위한 점화식으로 가장 옳은 것은? (단, 테이블 D는 동적 프로그래밍을 위한 (n+1)×(n+1) 크기의 테이블이고, Di,j는 지역 (1, 1)에서 지역 (i,j)까지 이동하면서 얻을 수 있는 최대 청소 점수의 합이다.)
<보기> 행렬 M (예: M3,1=4)
1
2
3
4
1
5
3
2
1
2
1
9
1
2
3
4
2
8
1
4
1
1
3
7
1
Di,j={0Mi,j+min(Mi,j−1,Mi−1,j)if i=0 or j=0,otherwise.
2
Di,j={0Mi,j+max(Mi,j−1,Mi−1,j)if i=0 or j=0,otherwise.
3
Di,j={0Mi,j+min(Di,j−1,Di−1,j)if i=0 or j=0,otherwise.
4
Di,j={0Mi,j+max(Di,j−1,Di−1,j)if i=0 or j=0,otherwise.
해설
옳은 점화식은 Di,j=Mi,j+max(Di,j−1,Di−1,j)이다.
지역 (i, j)에는 왼쪽 (i, j−1)이나 위쪽 (i−1, j)에서만 올 수 있으므로, 두 지역까지의 누적 최대 점수 중 큰 쪽에 현재 지역의 점수를 더한다.
0행·0열을 0으로 두면 첫 행·첫 열도 같은 식으로 처리된다.
M의 이웃 값 중 큰 쪽을 더하는 식: 바로 앞 지역 하나의 점수만 보아 출발점부터 누적된 합을 반영하지 못한다.
M의 이웃 값 중 작은 쪽을 더하는 식: 누적 합을 쓰지 않을 뿐 아니라 작은 쪽을 고른다.
D의 이웃 값 중 작은 쪽을 더하는 식: 누적 합은 쓰지만 최소 점수 경로를 구하게 된다.