시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 260 | 97 | 69 | 37.705% |
오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
양의 정수로 이루어진 n × n 행렬 m이 주어진다. 행렬의 왼쪽 위에서 시작해 한 칸씩 이동해 오른쪽 아래까지 도달한다. 이 과정에서 방문한 칸에 있는 수들을 더한 값이 이 경로의 합이다. 이동 규칙은 다음과 같다.
행렬의 원소 (1, 1)에서 (n, n)으로 이동하는 모든 경로의 점수 중 가장 높은 점수를 구하는 행렬 경로 문제 의사코드는 아래와 같다. 출발 원소 (1, 1)에서 출발해서 P개의 중간 원소 중 적어도 한 개의 원소를 반드시 거친 후 도착 원소 (n, n)에 도달하는 가장 높은 점수를 구해서 우리 서준이를 도와주자.
행렬 경로 문제 동적 프로그래밍 의사 코드는 다음과 같다.
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]); return d[n, n]; }
첫째 줄에 행렬의 크기 n(5 ≤ n ≤ 1,000)이 주어진다.
그 다음 n개의 줄에는 각 줄마다 행렬의 각 행을 나타내는 n개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 1 이상 100,000 이하이다.
그 다음 줄에 P가 주어진다. (1 ≤ P ≤ n2 - 2)
그 다음 P개의 줄에는 각 줄마다 서로 다른 중간 원소의 행 번호 ri와 열 번호 ci가 주어진다.(1 ≤ ri, ci ≤ n, (ri, ci) ≠ (1, 1), (ri, ci) ≠ (n, n))
출발 원소 (1, 1)에서 출발해서 P개의 중간 원소 중 적어도 한 개의 원소를 반드시 거친 후 도착 원소 (n, n)에 도달하는 가장 높은 점수를 출력한다.
5 1 1 1 1 7 1 1 1 3 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 4 2 3 3 2 4 1 4 3
11
출발 원소 (1, 1)에서 원소 (3, 2), (4, 3)을 거쳐서 도착 원소 (5, 5)에 도달하는 가장 높은 점수는 11이다.