ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • DP_백준_스티커_9465
    Algorithm 2018. 8. 16. 15:03


    순서가 정해져 있지 않다는것은 우리가 스티커를 때는 순서를 정할 수 있다. 즉 왼쪽부터 한 열씩 스티커를 어떻게 뜯을지를 결정한다. 이 문제 또한 길이가 N 일때 마지막 상태가 정해져 있지 않아서 2차원 배열로 마지막 상태를 표현한다.


    1. 정의 : dp[N][M] : 2*N에서 얻을 수 있는 최대점수, M=0(뜯지 않음), M=1(위쪽 스티커를 뜯음), M=2(아래쪽 스티커를 뜯음)

    2. 점화식 : dp[N][0] = max(dp[N-1][0], dp[N-1][1], dp[N-1][2])

                  dp[N][1] = max(dp[N-1][0], dp{n-1][2]) + value[0][N]

                  dp[N][2] = max(dp[N-1][0], dp[N-1][1]) +value[1][N]

    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
    #include <iostream>
    using namespace std;
     
    int max(int a, int b, int c) {
        int tmp = a;
        if (tmp < b)
            tmp = b;
        if (tmp < c)
            tmp = c;
        return tmp;
    }
     
    int main() {
        int count;
        cin >> count;
        for (int q = 0; q < count; q++) {
            int num; // N Length
            cin >> num;
     
            int ** value = new int*[2]; //Input
            int ** dp = new int*[num]; // DP memoization
     
            for (int i = 0; i < 2; i++) {
                value[i] = new int[num];
            }
            for (int i = 0; i < num; i++) {
                dp[i] = new int[3];
            }
            //Create
     
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < num; j++) {
                    cin >> value[i][j];
                }
            }
                // Input
     
            dp[0][0= 0;
            dp[0][1= value[0][0];
            dp[0][2= value[1][0];
            //Initialize
     
            for (int i = 1; i < num; i++) {
                dp[i][0= max(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]);
                dp[i][1= max(dp[i - 1][0], dp[i - 1][2], 0+ value[0][i];
                dp[i][2= max(dp[i - 1][0], dp[i - 1][1], 0+ value[1][i];
            }
            //Calculate
            cout << max(dp[num - 1][0], dp[num - 1][1], dp[num - 1][2]) << endl;
        }
        return 0;
    }
    cs


    'Algorithm' 카테고리의 다른 글

    DP_백준_가장 긴 증가하는 부분 수열_LIS_11053  (0) 2018.08.16
    DP_백준_포도주 시식_2156  (0) 2018.08.16
    DP_백준_이친수_2193  (0) 2018.08.16
    DP_백준_오르막 수_11057  (0) 2018.08.16
    DP_백준_쉬운 계단 수_10844  (0) 2018.08.16
Designed by Tistory.