[BOJ] 9465. 스티커(DP 기초)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

귀여운 스티커 문제다...ㅋㅋㅋㅋㅋ

가지고 싶다~~~!

DP[i][j]에 해당 위치에 있는 스티커까지 얻을 수 있는 최대 점수를 저장하면 된다.

입력이 아래와 같다면

50 10 100 20 40

30 50 70 10 60

각 스티커 점수를 담은 A 배열과 얻을 수 있는 최대 점수를 저장하는 dp 배열이 필요하다.

먼저 dp[1][1], dp[2][1]은 자신을 선택하는 것이 최대 점수이므로 

편의를 위해 먼저 자기 자신의 점수를 저장한다. (직관적으로 해결할 수 있는 작은 문제)

이제 dp[1][2]를 보자.

dp[1][2] 위치까지에 있는 스티커를 사용하여 얻을 수 있는 최대 점수를 구해야 한다.

dp[1][2]의 최대 점수를 구하기 위해서는 dp[][]에서 연두색 박스에 있는 점수들의 최댓값(30)에

A[1][2]인 10을 더해주면 된다. = 40

* A[1][2] 스티커를 선택했을 때, 선택할 수 있는 스티커들 중 얻을 수 있는 최대 점수를 가진 스티커를 선택해야

  dp[1][2]가 최댓값을 얻을 수 있으므로 이와 같은 동작이 이루어 진다. (글로 설명하기가 힘드네ㅠㅠ)

다음 dp[2][2]를 봐보자.

마찬가지로 dp[2][2] 위치까지에 있는 스티커를 사용하여 얻을 수 있는 최대 점수를 구해야 한다.

dp[2][2]의 최대 점수를 구하기 위해서는 dp[][]에서 연두색 박스에 있는 점수들의 최댓값(50)에

A[2][2]인 50을 더해주면 된다. = 100

* dp의 특성을 잘 이해한다면 충분히 이해할 수 있을 것이라고 생각한다.

조.. 조금만 더 진행해보자.

dp[1][3]을 보자.

dp[1][3] 위치까지에 있는 스티커를 사용하여 얻을 수 있는 최대 점수를 구해야 한다.

dp[1][3]의 최대 점수를 구하기 위해서는 dp[][]에서 연두색 박스에 있는 점수들의 최댓값(100)에

A[1][3]인 100을 더해주면 된다. = 200

* 여기서 연두색 박스에 있는 점수들의 최댓값을 저장한 DP[2][2]는 

   A[1][1], A[2][2] 스티커 점수의 합을 의미한다.

마지막으로 dp[2][3]을 보자.

dp[2][3] 위치까지에 있는 스티커를 사용하여 얻을 수 있는 최대 점수를 구해야 한다.

dp[2][3]의 최대 점수를 구하기 위해서는 dp[][]에서 연두색 박스에 있는 점수들의 최댓값(50)에

A[2][3]인 70을 더해주면 된다. = 120

* 여기서 연두색 박스에 있는 점수들의 최댓값을 저장한 DP[1][1]은 

   A[1][1] 스티커만 사용하였다.

부족한 설명이지만..

훗날 다시 참고하거나 누군가가 보았을 때,

바로 이해할 수 있었으면 좋겠다.. ㄹ_ㄹ

#. Code

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

#include <cstdio> #include <vector> #include <algorithm> using namespace std;   int A[3][100001], DP[3][100001];   void solve() {     int n, i, j, mxup = 0, mxdw = 0, res = 0;     scanf("%d", &n);       for (i = 1; i <= 2; i++)         for (j = 1; j <= n; j++)             scanf("%d", &A[i][j]);       for (j = 1; j <= n; j++) {         for (i = 1; i <= 2; i++) {             if (i == 1) // down                 DP[i][j] = max(max(mxdw, mxup), DP[2][j - 1]) + A[i][j];             else if (i == 2) // up                 DP[i][j] = max(max(mxdw, mxup), DP[1][j - 1]) + A[i][j];         }           mxdw = max(mxdw, DP[2][j - 1]);         mxup = max(mxdw, DP[1][j - 1]);     }       printf("%d\n", max(DP[1][n], DP[2][n])); }   int main(void) {     int tc;     //freopen("input.txt", "rt", stdin);     scanf("%d", &tc);       while (tc--)         solve();       return 0; } Colored by Color Scripter

cs

line 20) 위에서 설명한 연두색 박스에 있는 점수들의 최댓값에 A[i][j]를 더해준다.

line 21) 아랫줄에 있는 스티커의 경우

line 25~26) 윗줄, 아랫줄 스티커에 대한 동작을 모두 완료하면 각 줄의 최댓값을 저장해준다.

    * 연두색 박스에서 대각선[i-1[j-1]에 있는 데이터의 참조가 복잡하여 이렇게 분리하여 구현하였다.

       더 좋은 방법이 있다면 알려주세요오~!