24418번 - 알고리즘 수업 - 행렬 경로 문제 1

문제

오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

양의 정수로 이루어진 n × n 행렬 m이 주어진다. 행렬의 왼쪽 위에서 시작해 한 칸씩 이동해 오른쪽 아래까지 도달한다. 이 과정에서 방문한 칸에 있는 수들을 더한 값이 이 경로의 합이다. 이동 규칙은 다음과 같다.

• 오른쪽이나 아래쪽으로만 이동할 수 있다.
• 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다.

행렬의 원소 (1, 1)에서 (n, n)으로 이동하는 모든 경로의 점수 중 가장 높은 점수를 구하는 행렬 경로 문제 의사코드는 아래와 같다. 재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자. 행렬의 크기 n과행렬 m이 주어진 경우 코드1 코드2 실행 횟수를 출력하자.

행렬 경로 문제 재귀호출 의사 코드는 다음과 같다.

matrix_path(m[][], n) { # (1, 1)에서 (n, n)에 이르는 최고 점수를 구한다.
 return matrix_path_rec(m, n, n);
}
matrix_path_rec(m[][], i, j) { # (1, 1)에서 (i, j)에 이르는 최고 점수를 구한다.
 if (i == 0 or j == 0) then
 return 0; # 코드1
 else
 return (mij + (max(matrix_path_rec(m, i-1, j), matrix_path_rec(m, i, j-1))));
}

행렬 경로 문제 동적 프로그래밍 의사 코드는 다음과 같다.

matrix_path(m[][], n) { # (1, 1)에서 (n, n)에 이르는 최고 점수를 구한다.
 for i <- 0 to n
 d[i, 0] <- 0;
 for j <- 1 to n
 d[0, j] <- 0;
 for i <- 1 to n
 for j <- 1 to n
 d[i, j] <- mij + max(d[i - 1, j], d[i, j - 1]); # 코드2
 return d[n, n];
}

입력

첫째 줄에 행렬의 크기 n(5 ≤ n ≤ 15)이 주어진다.

그 다음 n개의 줄에는 각 줄마다 행렬의 각 행을 나타내는 n개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 1 이상 100,000 이하이다.

출력

코드1 코드2 실행 횟수를 한 줄에 출력한다.

제한

힌트