BOJ 2096 - 내려가기 | 방과후 블로그

문제

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

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

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

결국 중요한 것은 무엇을 기억해야 중복 계산이 사라지는지 찾는 일이다. 상태 정의가 맞으면 전이 자체는 비교적 자연스럽게 따라오는 경우가 많다.

코드

#include <iostream>
 
using namespace std;
 
int dp_Max[3];
int dp_Min[3];
int arr[3];
 
void solve() {
    int N = 0;
    int temp0, temp1, temp2;
    cin >> N;
 
    cin >> dp_Max[0] >> dp_Max[1] >> dp_Max[2];
    dp_Min[0] = dp_Max[0]; dp_Min[1] = dp_Max[1]; dp_Min[2] = dp_Max[2];
 
    for (int i = 1; i < N; i++) {
        cin >> arr[0] >> arr[1] >> arr[2];
 
        temp0 = dp_Max[0]; temp1 = dp_Max[1]; temp2 = dp_Max[2];
        dp_Max[0] = max(temp0, temp1) + arr[0];
        dp_Max[1] = max(max(temp0, temp1), temp2) + arr[1];
        dp_Max[2] = max(temp1, temp2) + arr[2];
 
        temp0 = dp_Min[0]; temp1 = dp_Min[1]; temp2 = dp_Min[2];
        dp_Min[0] = min(temp0, temp1) + arr[0];
        dp_Min[1] = min(min(temp0, temp1), temp2) + arr[1];
        dp_Min[2] = min(temp1, temp2) + arr[2];
    }
 
    int max_Num = max(max(dp_Max[0], dp_Max[1]), dp_Max[2]);
    int min_Num = min(min(dp_Min[0], dp_Min[1]), dp_Min[2]);
    cout << max_Num << " " << min_Num << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    solve();
 
    return 0;
}

복잡도

시간 복잡도: 각 행의 세 칸 상태를 한 번씩 갱신하므로 $O(N)$ 이다.
공간 복잡도: 이전 행의 최댓값/최솟값만 유지하므로 $O(1)$ 이다.

마무리

DP 문제는 상태를 잘 정의하는 순간 절반은 끝난 셈이다. 어떤 값을 기억해야 같은 계산을 반복하지 않는지만 잡으면 흐름이 보인다.

BOJ 2096 - 내려가기

문제

입력

출력

풀이

코드

복잡도

마무리

문제#

입력#

출력#

풀이#

코드#

복잡도#

마무리#

문제

입력

출력

풀이

코드

복잡도

마무리