[백준 2096] 내려가기_dp(c++)

[문제]

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

2096번: 내려가기

[접근법]

• BFS랑 DP를 섞어서 접근할 생각으로 풀었다..
• 풀다보니 메모리제한이 4MB인걸 보고 절망..
• DP만으로 풀어야 한다는것을 깨달음..(친구의 도움을 받았다ㅠㅠ)

[문제풀이]

• 구하고자 하는 값이 최대값과 최소값이므로, 2차원배열로 만들었다. (배열을 n x 3으로 나면 메모리 초과가 난다그래서 1x3 크기의배열을 만들어서 계속 갱신하는 식으로 풀었다.)
• dp1의 min, max값을 가지고 dp2의 값을 갱신한다. 
• 내려갈때의 경우의 수가 3가지 이므로 조건문을 3가지로 나눴다.
• dp2[0]의 min값을 구하기 위해서는 dp1[0][0]과 dp1[1][0] 중 최소값을 가져와 dp2[0]값과 더하면된다.(max도 마찬가지이다) -> 이런식으로 계속 진행

[전체코드]

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    int dp1[3][2];//min, max저장
    int dp2[3][2];
    
    for(int i = 0; i<3; i++){
        cin >> dp1[i][0];
        dp1[i][1] = dp1[i][0];
    }
    
    for(int i = 1; i < n; i++){
        for(int j = 0 ; j<3; j++){
            int tmp;
            cin >> tmp;
            
            if(j == 0){
                dp2[j][0] = min(dp1[j][0], dp1[j+1][0]) + tmp; //최소값
                dp2[j][1] = max(dp1[j][1] , dp1[j+1][1]) + tmp;
            }else if(j==1){
                dp2[j][0] = min(dp1[j-1][0], min(dp1[j][0], dp1[j+1][0])) + tmp; //최소값
                dp2[j][1] = max(dp1[j-1][1], max(dp1[j][1], dp1[j+1][1])) + tmp;
            }else if(j==2){
                dp2[j][0] = min(dp1[j][0], dp1[j-1][0]) + tmp; //최소값
                dp2[j][1] = max(dp1[j][1] , dp1[j-1][1]) + tmp;
            }
            
        }
        
        for(int j = 0; j < 3; j++){
            dp1[j][0] = dp2[j][0];
            dp1[j][1] = dp2[j][1];
        }
    }
    
    cout << max(dp1[0][1], max(dp1[1][1], dp1[2][1])) << " " << min(dp1[0][0], min(dp1[1][0], dp1[2][0]));
    return 0;
}