[Algorithm] 백준 2096 내려가기 문제풀이(Feat. 메모리초과, 메모리 계산법)

내 생각

다이나믹 프로그래밍에 점화식은 바로 세울수 있었다. 너무 기쁜나머지 메모리에 대한 에러를 해결하는데 오래걸렸다... 하나가 되면 하나가 안되는 매직. 아이디어는 떠올렸으니 메모리 제한에 대해 계산하는 법을 정리하겠다. 

---

메모리 계산하기

대략적인 메모리 계산법은 다음과 같다. 

1MB = 1000KB

1KB = 1000byte

따라서 1MB = 1000000byte이다. 

과연 1MB에서 int형 배열은 몇개까지 선언할 수 있을까??

int는 4바이트이기 때문에 1000000/4 = 250000개 선언할 수 있다. 

---

코드

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

int dp_max[3],dp_min[3];

int max(int a, int b)
{
   return  a > b ? a : b;
}

int min(int a, int b)
{
   return  a < b ? a : b;
}

int main()
{
    int n;
    scanf("%d", &n);
    
    for(int i = 1; i <= n; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        if(i == 1)
        {
            dp_min[0] = a;
            dp_min[1] = b;
            dp_min[2] = c;
            
            dp_max[0] = a;
            dp_max[1] = b;
            dp_max[2] = c;
        }
        else
        {
            int dp_maxTemp0, dp_maxTemp1, dp_maxTemp2;
            dp_maxTemp0 = max(dp_max[0] + a, dp_max[1]+ a);
            
            dp_maxTemp1 = max(dp_max[0] + b, dp_max[1] + b);
            dp_maxTemp1 = max(dp_maxTemp1, dp_max[2]+ b);
            dp_maxTemp2 = max(dp_max[1]+ c, dp_max[2]+ c);
            
            int dp_minTemp0, dp_minTemp1, dp_minTemp2;
            dp_minTemp0 = min(dp_min[0] + a, dp_min[1]+ a);
            
            dp_minTemp1 = min(dp_min[0] + b, dp_min[1] + b);
            dp_minTemp1 = min(dp_minTemp1, dp_min[2]+ b);
    
            dp_minTemp2 = min(dp_min[1]+ c, dp_min[2]+ c);
            
            
            dp_max[0] = dp_maxTemp0;
            dp_max[1] = dp_maxTemp1;
            dp_max[2] = dp_maxTemp2;
            
            dp_min[0] = dp_minTemp0;
            dp_min[1] = dp_minTemp1;
            dp_min[2] = dp_minTemp2;
                
        }
        
        
    }
    sort(dp_max, dp_max + 3);
    sort(dp_min, dp_min + 3);
    
    printf("%d %d\n", dp_max[2], dp_min[0]);
    
    
}