[2096번] 내려가기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. DP의 메모리 절약 방법

보통은 DP또한 map과 동일한 배열 크기로 만들어 진행한다.

하지만 이 문제의 메모리 제한은 4mb이다.

int형이 4byte이고 map만해도 400020 * 4이니 1,600,080b =  1563kb = 1.5mb이다.

따라서 maxDP와 minDP를 만든다면 당연히 메모리 초과가 날 것이니 이 문제는

DP의 성질을 이용해야 한다.

DP는 이전 단계의 값을 이용하여 푸는 것이기에 애초에 첫 DP값, 두번째 DP값 등등은 필요 없어지게 된다.

단지 전 단계의 DP값만 있으면 된다.

따라서

    int maxt1, maxt2, maxt3;

    int mint1, mint2, mint3;

    int maxdp1, maxdp2, maxdp3;

    int mindp1, mindp2, mindp3;

이런식으로 12가지의 dp값만 있으면 되는데 

위의 6가지 dp값은 temp값으로 dp를 계산할 때 계속 이용되는 값이고 아래 6가지 값은 실제 dp로 이용될 값이다.

저 값들은 배열로 maxdp[3], mindp[3] 이런식으로 만들어 이용한다면 더 깔끔한 코드가 완성될 수 있다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

#include <iostream> #include <cstdio>   #define max(a,b)(a>b?a:b) #define min(a,b)(a<b?a:b)   using namespace std;   int map[100005][4];   int main() {     int n;     int i = 1, j = 1;       int maxt1, maxt2, maxt3;     int mint1, mint2, mint3;       int maxdp1, maxdp2, maxdp3;     int mindp1, mindp2, mindp3;       scanf("%d", &n);       for (i = 1; i <= n; i++)         for (j = 1; j <= 3; j++)             scanf("%d", &map[i][j]);       maxdp1 = map[1][1];     maxdp2 = map[1][2];     maxdp3 = map[1][3];       mindp1 = map[1][1];     mindp2 = map[1][2];     mindp3 = map[1][3];       for (i = 2; i <= n; i++)     {         maxt1 = max(maxdp1, maxdp2) + map[i][1];         maxt2 = max(max(maxdp1, maxdp2), maxdp3) + map[i][2];         maxt3 = max(maxdp2, maxdp3) + map[i][3];           mint1 = min(mindp1, mindp2) + map[i][1];         mint2 = min(min(mindp1, mindp2), mindp3) + map[i][2];         mint3 = min(mindp2, mindp3) + map[i][3];           maxdp1 = maxt1;         maxdp2 = maxt2;         maxdp3 = maxt3;           mindp1 = mint1;         mindp2 = mint2;         mindp3 = mint3;     }       printf("%d %d", max(max(maxdp1, maxdp2), maxdp3), min(min(mindp1, mindp2), mindp3));       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

아래 코드는 메모리 초과를 발생시키는 자주 이용하던 DP 모습이다.

#include <iostream>
#include <cstdio>
 
#define max(a,b)(a>b?a:b)
#define min(a,b)(a<b?a:b)
 
using namespace std;
 
int map[100005][4];
int MAXDP[100005][4];
int MINDP[100005][4];
 
int main()
{
    int n;
    int i = 1, j = 1;
 
    scanf("%d", &n);
 
    for(i = 1; i <= n ; i ++)
        for(j = 1; j <= 3; j++)
            scanf("%d", &map[i][j]);
    
    MAXDP[1][1] = map[1][1];
    MAXDP[1][2] = map[1][2];
    MAXDP[1][3] = map[1][3];
 
    MINDP[1][1] = map[1][1];
    MINDP[1][2] = map[1][2];
    MINDP[1][3] = map[1][3];
 
    for (i = 2; i <= n; i++)
    {
        MAXDP[i][1] = max(MAXDP[i - 1][1], MAXDP[i - 1][2]) + map[i][1];
        MAXDP[i][2] = max(max(MAXDP[i - 1][1], MAXDP[i - 1][2]), MAXDP[i - 1][3]) + map[i][2];
        MAXDP[i][3] = max(MAXDP[i - 1][2], MAXDP[i - 1][3]) + map[i][3];
 
        MINDP[i][1] = min(MINDP[i - 1][1], MINDP[i - 1][2]) + map[i][1];
        MINDP[i][2] = min(min(MINDP[i - 1][1], MINDP[i - 1][2]), MINDP[i - 1][3]) + map[i][2];
        MINDP[i][3] = min(MINDP[i - 1][2], MINDP[i - 1][3]) + map[i][3];
    }
 
    printf("%d %d", max(max(MAXDP[n][1], MAXDP[n][2]), MAXDP[n][3]), min(min(MINDP[n][1], MINDP[n][2]), MINDP[n][3]));
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>