백준 27210, 신을 모시는 사당

개요

문제 링크
골드 5, DP
1과 2로 이루어진 수열의 연속 부분수열의 1,2 개수차이의 최댓값

---

접근

1. 저장할 값이 바로 생각나지는 않는 좋은 DP문제, 개수 차이의 최댓값을 구한다? 하면 dp에 저장할 값은 개수차이의 최댓값이겠구나.

2. 그럼 이걸 어떻게 갱신을 해야 하나? 1차원 dp는 사용해서 안되고 2차원 dp를 사용해야겠음. 이유는? 1과 2에 대해 따로 값을 구해줘야 함.

3. 따로 한다는 게 무엇을 따로 해야할까? 하고 생각하다가 아하, 1이 많은 배열과 2가 많은 배열을 구분하면 되겠구나 싶었음.

4. 갱신은 어떻게? a[i]=1일때 1이 많은 배열의 길이는 +1해주면 되고, 2가 많은 배열은 -1을 해주면 되는데 음수는 없으니까 양수만 가져오면 됨. 말 대신 아래 예시를 보자.

   편의상 1이 많은 배열의 최대개수차이 = dp[i][1] = 1배열길이 라 하자.

   i	1	2	3	4	5	6	7	8	9
   a[i]	2	2	2	1	1	1	1	2	2
   dp[i][1]	max(0,이전의1배열길이-1) =max(0,dp[i-1][1]-1) =0	0	0	1	2	3	dp[i-1][1]+1 =4	3	2
   dp[i][2]	이전의2배열길이+1 =dp[i-1][2]+1 =1	2	3	2	1	0	max(0, dp[i-1][2]-1) =0	1	2

5. i=7일 때를 중심으로 보자. 먼저 1배열, 1이 등장하면 dp[i][1] = dp[i-1][1] + 1을 해주면 된다. 왜냐, 그게 최대이기 때문. 왜 최대이냐? 왜 dp[i-1][2]-1은 비교하지 않느냐? dp[i-1][2]는 2가 많은 배열의 길이이다. dp[i][1]이 max(dp[i-1][1]+1, dp[i-1][2]-1)이라면 dp[i][1]에 2배열의 속성을 저장할 수 있다. 즉 2가 많은 배열의 개수차이를 잘못 저장할 수 있다는 것이다.

   여기서 다른 dp와의 차이점이 잘 드러난다. 왜 좋은 문제냐?에 대한 대답이기도 함. 기존의 문제들은 dp[n][2]를 만들면 1또는 2가 끝값인 경우의 최댓값을 다루고, 두 값을 모두 이용해 업데이트 한다. 그런데 여기서는 1또는 2가 많은 경우의 최댓값을 다룬다. 대상이 조금 더 추상적이라 이 차이를 구분하는 과정이 조금 까다롭다.

6. 다음 2배열, 1이 등장하면 dp[i][2] = max(0, dp[i-1][2]-1)을 해주면 됨. 앞에서 개수차이가 0이 되면 없느니만 못하다는 것은 설명했고, dp[i-1][1]+1을 안하는 이유는 위에서 말한대로 2배열길이를 저장한 dp[i][2]에 1배열의 속성이 저장될 수 있기 때문이다.

7. 마지막으로 연속부분수열의 시작과 끝은 모든 점이 될 수 있으니까 answer = max(dp[n][1], dp[n][2])가 아니다. for 문을 돌면서 모두 업데이트 해줘야 한다.

---

Pseudo code

for (i = 1~n)
    if (a[i] = 1)
        dp[i][1] = dp[i-1][1]+1
        dp[i][2] = max(0, dp[i-1][2]-1)
    else
        dp[i][2] = dp[i-1][2]+1
        dp[i][1] = max(0, dp[i-1][1]-1)

---

Source code

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n+1], dp[n+1][3];
    dp[0][1] = 0;
    dp[0][2] = 0;
    int ans = 0;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        int x, y;
        x = a[i], y = 3-a[i];

        dp[i][x] = dp[i-1][x]+1;
        dp[i][y] = max(0,dp[i-1][y]-1);

        ans = max(ans, dp[i][1]);
        ans = max(ans, dp[i][2]);
    }
    cout << ans;
}