로봇 청소기가 청소할 지역들을 표현한 n\times n 크기의 행렬 M… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 알고리즘] 26년 1회차
로봇 청소기가 청소할 지역들을 표현한 n×nn\times n 크기의 행렬 MM이 있다. <보기>는 4 × 4 크기의 행렬 MM에 대한 예시로, 행렬의 각 원소 Mi,jM_{i,j}는 지역 (i, j)(i,\ j)을 청소했을 때 얻을 수 있는 양의 정수인 청소 점수이다. 한편, 로봇 청소기는 오른쪽이나 아래쪽으로만 이동할 수 있으며, 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다. 로봇 청소기가 지역 (1, 1)에서 청소를 시작하여 지역 (n, n)(n,\ n)에 도착할 때까지, 가장 많은 청소 점수를 얻고자 한다. 동적 프로그래밍(dynamic programming)을 이용하여 이 문제를 해결하기 위한 점화식으로 가장 옳은 것은? (단, 테이블 DD는 동적 프로그래밍을 위한 (n+1)×(n+1)(n+1)\times(n+1) 크기의 테이블이고, Di,jD_{i,j}는 지역 (1, 1)에서 지역 (i, j)(i,\ j)까지 이동하면서 얻을 수 있는 최대 청소 점수의 합이다.)
<보기>
행렬 MM
(예: M3,1=4M_{3,1}=4)
1234
15321
21912
34281
41137
1
Di,j={0if i=0 or j=0,Mi,j+min⁡(Mi,j−1, Mi−1,j)otherwise.D_{i,j}=\begin{cases}0 & \text{if } i=0 \text{ or } j=0,\\ M_{i,j}+\min(M_{i,j-1},\ M_{i-1,j}) & \textit{otherwise.}\end{cases}
2
Di,j={0if i=0 or j=0,Mi,j+max⁡(Mi,j−1, Mi−1,j)otherwise.D_{i,j}=\begin{cases}0 & \text{if } i=0 \text{ or } j=0,\\ M_{i,j}+\max(M_{i,j-1},\ M_{i-1,j}) & \textit{otherwise.}\end{cases}
3
Di,j={0if i=0 or j=0,Mi,j+min⁡(Di,j−1, Di−1,j)otherwise.D_{i,j}=\begin{cases}0 & \text{if } i=0 \text{ or } j=0,\\ M_{i,j}+\min(D_{i,j-1},\ D_{i-1,j}) & \textit{otherwise.}\end{cases}
4
Di,j={0if i=0 or j=0,Mi,j+max⁡(Di,j−1, Di−1,j)otherwise.D_{i,j}=\begin{cases}0 & \text{if } i=0 \text{ or } j=0,\\ M_{i,j}+\max(D_{i,j-1},\ D_{i-1,j}) & \textit{otherwise.}\end{cases}
해설

옳은 점화식은 Di,j=Mi,j+max⁡(Di,j−1, Di−1,j)D_{i,j}=M_{i,j}+\max(D_{i,j-1},\ D_{i-1,j})이다.

지역 (i, j)에는 왼쪽 (i, j−1)이나 위쪽 (i−1, j)에서만 올 수 있으므로, 두 지역까지의 누적 최대 점수 중 큰 쪽에 현재 지역의 점수를 더한다.

0행·0열을 0으로 두면 첫 행·첫 열도 같은 식으로 처리된다.

  • M의 이웃 값 중 큰 쪽을 더하는 식: 바로 앞 지역 하나의 점수만 보아 출발점부터 누적된 합을 반영하지 못한다.
  • M의 이웃 값 중 작은 쪽을 더하는 식: 누적 합을 쓰지 않을 뿐 아니라 작은 쪽을 고른다.
  • D의 이웃 값 중 작은 쪽을 더하는 식: 누적 합은 쓰지만 최소 점수 경로를 구하게 된다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 서울시 알고리즘] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 알고리즘 기출문제 암기장 전체 보기