백준 15645번 C++ 풀이

https://www.acmicpc.net/problem/15645

15645번: 내려가기 2

시간 제한	메모리 제한	solved.ac 티어
1초	512MB	실버 1

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

입력

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

출력

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

---

그간 학업으로 인해 PS문제를 잠시 내려놓고 지냈다가, 방학이후로 탱자탱자 놀았다. 뭔가 X되가는게 느껴져서 PS 재활훈련을 위해 랜덤 실버 문제 디펜스를 시작했다. 그래서 걸린게 실버1 DP문제... 억까하는게 분명하다.

잡설은 그만하고, DP문제임에도 이 문제는 상당히 웰노운? 같은 풀이법을 적용할 수 있다.

 

DP는 복잡한 문제를 작은문제에서 확장해나가는 것이다. 예제 케이스를 통해 살펴보자. 해당 케이스는 백준 예제 입력 케이스이다.

 

	0열	1열	2열
0행	1	2	3
1행	4	5	6
2행	4	9	0

0행에서 시작하여 내려오기 때문에 일단 0행만 살펴보도록 하자.

	0열	1열	2열
0행	1	2	3

어떻게 내려왔던, 각 열에 도착했을 때 만들 수 있는 최댓값은 다음과 같을 것이다. 시작지점이 곧 끝 지점이기 때문이다.

 

	0열	1열	2열
0행까지의 최대	1	2	3

 이제 1행까지 붙여서 생각해보자. 지금까지의 상황을 통해 조금 수정해보면

	0열	1열	2열
0행까지의 최대	1	2	3
1행	4	5	6

 이 될 것이다. 이제 다시 각 열에 도착했을 때 만들 수 있는 최댓값은 다음과 같을 것이다.

	0열	1열	2열
1행까지의 최대	6 (1 + 4, 2 + 4)	8 (1 + 5, 2 + 5, 3 + 5)	9 (2 + 6, 3 + 6)

우리가 알고자 하는건 결국 최댓값이기 때문에 어떻게 왔던간에 최댓값만 저장하면 된다. 이제 마지막 2행까지 따져보자. 역시 지금까지의 상황을 통해 수정하면 다음과 같아진다.

	0열	1열	2열
1행까지의 최대	6	8	9
2행	4	9	0

 또 각 열에 도착했을 때 만들 수 있는 최댓값을 구해보자.

	0열	1열	2열
2행까지의 최대	12 (6 + 4, 8 + 4)	18 (6 + 9, 8 + 9, 9 + 9)	9 (8 + 0, 9 + 0)

이제 각 열에 도달했을때 구할 수 있는 최댓값을 모두 구했다. 이중에서 제일 큰 값이 답이 될 것이고, 답은 18이다. 이를 코드로 구현하면 다음과 같다. 최솟값도 같은 방식으로 구하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
#define MAXVALUE (int)1e7

int row;
int col = 3;
vector<vector<int>> board;

void input() {
    cin >> row;
    board.resize(row);
    for (auto& line : board) {
        line.resize(col);
        for (int& x : line) cin >> x;
    }
}

int getMaxDp() {
    int dp[row][col];
    int dx[3] = {-1, 0, 1};
    int prev;
    for (int i = 0; i < col; i++) dp[0][i] = board[0][i];
    fill(&dp[1][0], &dp[row - 1][col], 0);

    for (int i = 1; i < row; i++) { // 라인 선택
        for(int j = 0; j < col; j++) { // 해당 라인에서 원소 선택
            for (int k = 0; k < 3; k++) { // 인덱스 변화량 선택
                prev = j + dx[k];
                if (prev < 0 || prev >= col) continue;

                dp[i][j] = max(dp[i][j], board[i][j] + dp[i - 1][prev]);
            }
        }
    }
    sort(dp[row - 1], dp[row - 1] + col);
    return dp[row - 1][col - 1];
}

int getMinDp() {
    int dp[row][col];
    int dx[3] = {-1, 0, 1};
    int prev;
    for (int i = 0; i < col; i++) dp[0][i] = board[0][i];
    fill(&dp[1][0], &dp[row - 1][col], MAXVALUE);

    for (int i = 1; i < row; i++) { // 라인 선택
        for(int j = 0; j < col; j++) { // 해당 라인에서 원소 선택
            for (int k = 0; k < 3; k++) { // 인덱스 변화량 선택
                prev = j + dx[k];
                if (prev < 0 || prev >= col) continue;

                dp[i][j] = min(dp[i][j], board[i][j] + dp[i - 1][prev]);
            }
        }
    }
    sort(dp[row - 1], dp[row - 1] + col);
    return dp[row - 1][0];
}

void sol() {
    int maxAnswer = getMaxDp();
    int minAnswer = getMinDp();
    cout << maxAnswer << ' ' << minAnswer;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    input();
    sol();
}

 

그래도 꽤 풀어본 유형의 DP문제라 다행이었다.