(C++) - 백준(BOJ) 2096번 : 내려가기

www.acmicpc.net/problem/2096

2096번: 내려가기

dp문제였습니다.

 

풀이방법

 메모리 제한이 4mb이므로 400만 byte크기 이하의 변수들을 선언해 사용해야 합니다. 이 문제는 10만개의 배열 이상 사용하지 않아도 되는 문제입니다. 

 

 1. 첫 번쨰 행의 세 수를 먼저 입력 받습니다. 그 후 d, d2배열에 각각 저장합니다.

 

 2. 현재 열이 0번째 열이면 이전의 행에서는 0,1번째 열 중 최대값에서 현재 열의 값을 더한값이 현재 열이 가질 수 있는 최댓값입니다. 현재 열이 1번째 열이면 이전의 행에서는 0,1,2번째 열 중 최대값에서 현재 열의 값을 더한값이 현재 열이 가질 수 있는 최댓값입니다. 이런식으로 각 행마다 열에 해당하는 최댓값과 최솟값을 구할 수 있습니다.

두 번째 행부터 n-1개의 세 수를 입력받으며 다음을 수행합니다.

 

    2-1. 현재 값들의 열마다 가질 수 있는 최댓값과 최솟값을 저장합니다. 대략적인 점화식의 형태는 다음과 같습니다.

    현재 행에 해당하는 열의 최댓값 : d[현재열] = max(d[이전열들 중 유효한 열들]) + 현재 점수

    현재 행에 해당하는 열의 최솟값 : d2[현재열] = min(d2[이전열들 중 유효한 열들]) + 현재 점수

 

    2-2. d, d2배열을 갱신해줍니다.

 

3. 각 열 중의 최댓값, 최솟값을 출력해줍니다.

    

   

 

Code

#include <bits/stdc++.h>
using namespace std;
int n, d[3], d2[3];
int main(){
    cin >> n;
    for(int i = 0; i < 3; i++) cin >> d[i], d2[i] = d[i];

    for(int i = 0; i < n - 1; i++){
        int a, b, c;
        cin >> a >> b >> c;
        int firstBig = max(d[0],d[1]) + a;
        int firstSmall = min(d2[0],d2[1]) + a;

        int secondBig = max({d[0],d[1],d[2]}) + b;
        int secondSmall = min({d2[0],d2[1],d2[2]}) + b;

        int thirdBig = max(d[1],d[2]) + c;
        int thirdSmall = min(d2[1],d2[2]) + c;

        d[0] = firstBig;
        d[1] = secondBig;
        d[2] = thirdBig;

        d2[0] = firstSmall;
        d2[1] = secondSmall;
        d2[2] = thirdSmall;
    }
    cout << max({d[0],d[1],d[2]}) << ' ' << min({d2[0],d2[1],d2[2]});
}