[Algorithm]Baekjoon 2096번 :: 내려가기

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

2096번: 내려가기

int maxDP[2][3] = { 0 };
int minDP[2][3] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n, a, b, c;
 
    cin >> n;
 
    int minResult = 0;
    int maxResult = 0;
    int curIndex = 1;
    int prevIndex = 0;
 
    for (int i = 1; i <= n; i++)
    {
        cin >> a >> b >> c;
 
        maxDP[curIndex][0] = max(maxDP[prevIndex][0], maxDP[prevIndex][1]) + a;
        maxDP[curIndex][1] = max(maxDP[prevIndex][0], max(maxDP[prevIndex][1], maxDP[prevIndex][2])) + b;
        maxDP[curIndex][2] = max(maxDP[prevIndex][1], maxDP[prevIndex][2]) + c;
                                         
        minDP[curIndex][0] = min(minDP[prevIndex][0], minDP[prevIndex][1]) + a;
        minDP[curIndex][1] = min(minDP[prevIndex][0], min(minDP[prevIndex][1], minDP[prevIndex][2])) + b;
        minDP[curIndex][2] = min(minDP[prevIndex][1], minDP[prevIndex][2]) + c;
 
        curIndex = (curIndex + 1) % 2;
        prevIndex = (prevIndex + 1) % 2;
    }
 
    cout << max(maxDP[n%2][0], max(maxDP[n%2][1], maxDP[n%2][2]))
        << ' ' << min(minDP[n%2][0], min(minDP[n%2][1], minDP[n%2][2]));
}

 

쉬운 난이도의 DP문제.

생각없이 DP배열을 N만큼 2개잡아줬다가 (최대값,최소값) 메모리초과가 떠서 아주 잠깐 고민하게 만든 문제다.

생각해보니 다른 문제들도 그렇고, 체크해야하는 범위까지의 배열만 잡아줘도 문제를 충분히 해결가능하다.

각 DP배열의 0번과 1번을 번갈아가며 공간을 활용해서 해결했다.

물론 아예 그냥 1차원배열로 표현해서 하는것도 가능하긴 한데, 이게 더 직관적이라 굳이 코드를 수정하지는 않았다.