알고리즘 분류별로 순서를 맞추는 건 포기했다. 차라리 나중에 글이 늘어나면 알고리즘 별로 시리즈를 따로 만들어야겠다.
1. 문제
n X m 크기의 금광이 있습니다. 금광은 1 X 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중에서 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.
만약 다음과 같이 3 X 4 크기의 금광이 존재한다고 가정합시다.
| 1 | 3 | 3 | 2 |
| 2 | 1 | 4 | 1 |
| 0 | 6 | 4 | 7 |
가장 왼쪽 위의 위치를(1, 1), 가장 오른쪽 아래 위치를 (n, m)이라고 할 때, 위 예시에서는 (2, 1) -> (3, 2) -> (3, 3) -(3, 4)의 위치로 이동하면 총 19만큼의 금을 채굴할 수 있으며, 이때의 값이 최댓값입니다.
2. 입력
- 첫째 줄에 테스트 케이스 T가 입력됩니다. (1 ≤ T ≤ 1000)
- 매 테스트 케이스는 첫째 줄에 n과 m이 공백으로 구분되어 입력됩니다. (1 ≤ n, m ≤ 20)
- 둘째 줄에는
n X m개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력됩니다. (1 ≤ 각 위치에 매장된 금의 개수 ≤ 100)
3. 출력
- 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력합니다. 각 테스트 케이스는 줄 바꿈을 이용해 구분합니다.
4. 풀이
- 이때까지 풀었던 문제와 유사했다.
- 며칠 전에 DP 문제를 많이 푼 게 도움이 됐다.
그 DP 문제가 책 뒤에 나오더라 - 현재 배열의 값에서 얻을 수 있는 최댓값을 갱신해가면서 마지막 열에서 최댓값인 행을 찾으면 된다.
dp[i][j] = max(dp[i, j-1], dp[i-1, j-1], dp[i+1, j-1]) + arr[i][j]를 해주었다.- 첫 행은
i-1이 존재하지 않고 마지막 행은i+1이 존재하지 않았다. - 예외처리 하기는 귀찮아서 그냥 모든 값이 0인 행을 위 아래로 추가했다.
- 정수 삼각형에서 비슷하게 풀어서 따라했다.
5. 처음 코드와 달라진 점
- 이게 첫 코드이긴 한데
- 위 아래로 빈 행 추가할 때 열은 추가 할 필요 없는데 추가했다거나
실제로 사용하진 않아서 메모리를 좀 더 쓸 분이다. - 위 아래로 빈 행을 추가해야 하는데 하나만 추가한다거나
20 X 20으로 꽉 채워서 주지 않는 한 문제가 생기진 않는다. 그 말은 꽉 채워서 주면 문제가 생긴다는 말이지..ㅎ - 1부터 시작하고
n까지 인지n-1까지 인지 조금 고민하긴 했다.머리가 슝슝 안 돌아가서 그렇다.
6. 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int arr[22][20];
int dp[22][20];
int main() {
int testCase;
cin >> testCase;
for (int i = 0; i < testCase; i++){
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
scanf_s("%d", &arr[i][j]);
}
}
for (int i = 1; i <= n; i++){
dp[i][0] = arr[i][0];
}
for (int j = 1; j < m; j++) {
for (int i = 1; i <= n; i++) {
dp[i][j] = max(max(dp[i + 1][j - 1], dp[i][j - 1]), dp[i - 1][j - 1]) + arr[i][j];
}
}
int maxValue = 0;
for (int i = 1; i <= n; i++){
maxValue = max(maxValue, dp[i][m - 1]);
}
cout << maxValue << endl;
}
}