ABOUT ME

Today
Yesterday
Total
  • 백준 2096번 : 내려가기
    알고리즘 공부 2020. 4. 8. 22:27

      만약 평범한 DP 문제였다면 그렇게 어렵지 않았을 것이다. 하지만 이 문제가 골드 4인 이유는 메모리 제한 때문이겠지! 그래서 원래라면 100000 * 3 짜리 2차원 array를 3개 정도 만들어서 기록하면서 진행했겠지만 그렇게하면 메모리 초과가 발생하기 때문에 한 줄 입력을 받을 때마다 바로 계산하는 방식으로 했다. 계산 자체는 그렇게 어렵지 않다. 문제에서 설명하는 그대로 max함수와 min함수를 이용해서 계산하면 된다.

    #include <stdio.h>
    #include <iostream>
     
    using namespace std;
    
    int n;
    int map[3], maxCnt[3], minCnt[3];
    
    int main()
    {
        cin >> n;
        
        for(int i = 0; i < n; i++)
        {
            cin >> map[0] >> map[1] >> map[2];
            
            if(i == 0)
            {
                maxCnt[0] = map[0];
                maxCnt[1] = map[1];
                maxCnt[2] = map[2];
                minCnt[0] = map[0];
                minCnt[1] = map[1];
                minCnt[2] = map[2];
            }
            else
            {
                int preMaxCnt[3] = { maxCnt[0], maxCnt[1], maxCnt[2] };
                maxCnt[0] = max(preMaxCnt[0], preMaxCnt[1]) + map[0];
                maxCnt[1] = max(max(preMaxCnt[0], preMaxCnt[1]), preMaxCnt[2]) + map[1];
                maxCnt[2] = max(preMaxCnt[1], preMaxCnt[2]) + map[2];
                
                int preMinCnt[3] = { minCnt[0], minCnt[1], minCnt[2] };
                minCnt[0] = min(preMinCnt[0], preMinCnt[1]) + map[0];
                minCnt[1] = min(min(preMinCnt[0], preMinCnt[1]), preMinCnt[2]) + map[1];
                minCnt[2] = min(preMinCnt[1], preMinCnt[2]) + map[2];
            }
        }
        
        cout << max(max(maxCnt[0], maxCnt[1]), maxCnt[2]) << " " << min(min(minCnt[0], minCnt[1]), minCnt[2]);
     
        return 0;
    }
Designed by Tistory.