백준 2096번, 내려가기(C, C++)

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

2096번: 내려가기

#include<iostream>
#define MAX 500000
using namespace std;


int dp[MAX][4] = {0};
int dp2[MAX][4] = {0};



int main(){
    int N;

    cin >> N;

    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= 3; j++){
        cin>>dp[i][j];
        }
    }


    for(int i = 1; i <= N; i++){
        for(int j = 1; j<=3; j++){
            if(j==1){
            dp[i][j] += max(dp[i-1][j], dp[i-1][j+1]);
            dp2[i][j] += min(dp[i-1][j], dp[i-1][j+1]);
            }
            if(j==2){
                dp[i][j] +=max((dp[i-1][j], dp[i-1][j+1]), dp[i-1][j-1]);
                dp2[i][j] +=min((dp[i-1][j], dp[i-1][j+1]), dp[i-1][j-1]);
            }
            if(j==3){
                dp[i][j] += max(dp[i-1][j-1], dp[i-1][j]);
                dp2[i][j] += min(dp[i-1][j-1], dp[i-1][j]);
            } 
        }
    }


    cout<<max((dp[N][1], dp[N][2]), dp[N][3])<<" ";
    cout<<min((dp2[N][1], dp2[N][2]), dp2[N][3]);

    return 0;
}

 

다이나믹 프로그래밍 방식으로 접근했는데

처음에 이런식으로 풀었다가 메모리 초과가 났다.

문제에서는 안나왔지만 메모리 4MB정도로 제한하고있다.

100000행 * 3 * 4byte = 1.2MB인데, 안 되는 이유를 찾아보니깐

int가 무조건 4byte가 아니라는 것.

아무튼 코드가 무겁기 때문에 줄일 필요가 있었다.

 

그래서 생각한 풀이는 2차원 배열을 갱신해서 푸는 것이 아닌

1차원 배열을 갱신해서 푸는 방식으로 돌렸다.

 

#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>


#define MAX 100001
using namespace std;

int arr1[MAX][4];
int dp[4];
int dp2[4];
int m1;
int m2;
int m3;



int main(){
    int N;

    cin >> N;

    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= 3; j++){
        cin>>arr1[i][j];
        }
    }
    for(int i = 1; i <= 3; i++){
        dp[i] = arr1[1][i];
    }


    for(int i = 2; i <= N; i++){
        m1 = dp[1];
        m2 = dp[2];
        m3 = dp[3];

        
        dp[1] = arr1[i][1] + max(m1,m2);
        dp[2] = arr1[i][2] + max({m1, m2, m3});
        dp[3] = arr1[i][3] + max(m2, m3);
    }
    int solution = max({dp[1], dp[2], dp[3]});
    cout<<solution<<' ';
     for(int i = 1; i <= 3; i++){
        dp2[i] = arr1[1][i];
    }


    for(int i = 2; i <= N; i++){
        m1 = dp2[1];
        m2 = dp2[2];
        m3 = dp2[3];

        dp2[1] = arr1[i][1] + min(m1, m2);
        dp2[2] = arr1[i][2] + min({m1, m2, m3});
        dp2[3] = arr1[i][3] + min(m2, m3);
    }

    

    int solution2 = min({dp2[1], dp2[2], dp2[3]});
    
    cout<<solution2;


    return 0;
}

 

 

사실 여기서도 문제를 여러번 틀렸다.

분명 코드를 맞게 작성했는데, 어디 부분에서 미스가났는 지 찾는데 시간이 걸렸다.

 

 

*m1 = dp[1], m2 = dp[2], m3 = dp[3]로 꼭 저장해줘야 한다!

 

 

그렇게 하지않으면 반복문이 dp[1]을 만들고 새롭게 갱신된 dp[1]이

dp[2]를 만들 때 들어가야하는 갱신되지않는 dp[1]자리에 들어가서

코드가 꼬여버리기 때문이다.