Even Idiots Can Make Game

백준 9465 S1 스티커

Date/Lastmod
Section
PS
Tags
dp
Title
백준 9465 S1 스티커
Ps-Tags
동적 계획법
Solved
04-23/25

#1 접근

동적 계획법 문제이며, 점화식을 세우는 것이 조금 까다롭다.

dp의 정의

dp[i]를 열 1 부터 i 까지 고려했을 때, i열에서

  • 아무것도 하지 않거나
  • 위쪽 스티커를 떼거나
  • 아래쪽 스티커를 떼었을 때

얻을 수 있는 점수의 최대값 이라고 정의한다.

편의를 위해 dp와 열거형을 다음과 같이 정의한다.

using ll = long long;
enum state {
  NO=0, UP, DO
};
vector<tuple<ll, ll, ll>> dp(n + 1);

이러면,

라고 표현할 수 있다.

#1 i = 2일때 예

한번 실제로 그림을 그려 보면서, i=2열에서 어떻게 되는지 확인해 보자.

(1) 2번 열에서 아무것도 하지 않은 경우 점수의 최대값(get<NO>(dp[2])) 구하기

중의 최대값이다.

(2) 2번 열에서 위쪽 스티커를 뗀 경우 점수의 최대값(get<UP>(dp[2])) 구하기

이 경우, 이전 열에서 위쪽 스티커를 떼지 않았다는 보장이 있어야 가능한 분기이다.
따라서,

중의 최대값이다.

(3) 2번 열에서 아래쪽 스티커를 뗀 경우 점수의 최대값(get<DO>(dp[2])) 구하기

이 경우, 이전 열에서 아래쪽 스티커를 떼지 않았다는 보장이 있어야 가능한 분기이다.
따라서,

중의 최대값이다.

#1 i = 1일때

초기 값인 i = 1 일 때에는 조금 다르다. 이전 열이 없으므로, 항상 모든 행동을 할 수 있다. 값은 다음과 같이 하나로 정해진다.

#1 점화식 일반화

따라서, dp[i] 는

i = 1 일 때

get<NO>(dp[1]) = 0;
get<UP>(dp[1]) = s1[1];
get<DO>(dp[1]) = s2[1];

i = k (k > 1) 일 때

get<NO>(dp[i]) 
  = max({get<NO>(dp[i - 1]), get<UP>(dp[i - 1]), get<DO>(dp[i - 1])})
get<UP>(dp[i]) 
  = max({get<NO>(dp[i - 1]),                   , get<DO>(dp[i - 1])})
get<DO>(dp[i]) 
  = max({get<NO>(dp[i - 1]), get<UP>(dp[i - 1]),                   })

라고 볼 수 있다.

그리고, 구하려는 값은 1부터 끝 열까지 진행한 후, 각 분기의 최대값이므로

max({get<NO>(dp[n]), get<UP>(dp[n]), get<DO>(dp[n])})

이다.

#1 코드

 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

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;
using ll = long long;

int main() {

  int T; cin >> T;
  for (int tc = 0; tc < T; ++tc) {

    // 입력
    int n; cin >> n;
    vector<long long> s1(n + 1, 0), s2(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
      cin >> s1[i];
    }
    for (int i = 1; i <= n; ++i) {
      cin >> s2[i];
    }

    enum state {
      NO=0,  // 아무것도 뜯지 않았을 때
      UP,    // 위쪽만 뜯었을 때
      DO     // 아래쪽만 뜯었을 때
    };

    // i 열에서, NO/UP/DO 판단을 내렸을 때 만들어지는 상태에 대해, i열 까지 각 상태에 대한 최대값
    vector<tuple<ll, ll, ll>> dp(n + 1);

    get<NO>(dp[1]) = 0;
    get<UP>(dp[1]) = s1[1];
    get<DO>(dp[1]) = s2[1];

    for (int i = 2; i <= n; ++i) {
      get<NO>(dp[i]) = max({get<NO>(dp[i - 1]), get<UP>(dp[i - 1]), get<DO>(dp[i - 1])});
      get<UP>(dp[i]) = max({get<NO>(dp[i - 1]),                     get<DO>(dp[i - 1])}) + s1[i];
      get<DO>(dp[i]) = max({get<NO>(dp[i - 1]), get<UP>(dp[i - 1])                    }) + s2[i];
    }

    cout << max({get<NO>(dp[n]), get<UP>(dp[n]), get<DO>(dp[n])}) << '\n';
  }
}
comments powered by Disqus