[백준 / BOJ] C++ 2096 내려가기

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

2096번: 내려가기

풀이

사실 한번 살펴보면 간단한 문제이다.

dp 문제들에 익숙해지면 조건식을 바로 알아챌 수 있다.

 

1. 별표 문양이 왼쪽에 있을 경우

dp[i][0] = arr[i][0] + max(dp[i - 1][0], dp[i - 1][1]); 
2. 별표 문양이 중앙에 있을 경우 
dp[i][1] = arr[i][1] + max(max(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][2]); 
3. 별표 문양이 오른쪽에 있을 경우
dp[i][2] = arr[i][2] + max(dp[i - 1][1], dp[i - 1][2]);

 

이 세가지 조건을 이용하여 문제를 쉽게 해결할 수 있다.

 

아래 코드를 확인해보자.

 

Code ( C++ )

#include <iostream>
#include <algorithm>
using namespace std;

int N;
int arr[3];
int max_dp[2][3] = {0,};
int min_dp[2][3] = {0,}; 

int main()
{
    cin >> N;

    for(int i = 0; i < N; i++)
    {
        cin >> arr[0] >> arr[1] >> arr[2];
        
        if(i == 0)
        {
            max_dp[0][0] = min_dp[0][0] = arr[0];
            max_dp[0][1] = min_dp[0][1] = arr[1];
            max_dp[0][2] = min_dp[0][2] = arr[2];
            continue;
        }

        max_dp[1][0] = arr[0] + max(max_dp[0][0], max_dp[0][1]);
        max_dp[1][1] = arr[1] + max(max(max_dp[0][0], max_dp[0][1]), max_dp[0][2]);
        max_dp[1][2] = arr[2] + max(max_dp[0][1], max_dp[0][2]);

        max_dp[0][0] = max_dp[1][0];
        max_dp[0][1] = max_dp[1][1];
        max_dp[0][2] = max_dp[1][2];

        min_dp[1][0] = arr[0] + min(min_dp[0][0], min_dp[0][1]);
        min_dp[1][1] = arr[1] + min(min(min_dp[0][0], min_dp[0][1]), min_dp[0][2]);
        min_dp[1][2] = arr[2] + min(min_dp[0][1], min_dp[0][2]);

        min_dp[0][0] = min_dp[1][0];
        min_dp[0][1] = min_dp[1][1];
        min_dp[0][2] = min_dp[1][2];
    }

    cout << max(max(max_dp[0][0], max_dp[0][1]), max_dp[0][2]) << ' ' << min(min(min_dp[0][0], min_dp[0][1]), min_dp[0][2]) << endl;
}