[백준(BOJ)] 9465번: 스티커 (C++)

입력

• 첫째줄: 테스트케이스 수
• 둘째줄: 한 줄에 있는 스티커 수
• 셋째줄: 스티커 별 점수

출력

• 각 테스트케이스에서 두 변을 공유하지 않는 스티커 점수의 최댓값

---

조건

• 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 됨
• 항상 S[0][0] 또는 S[1][0]부터 스티커를 떼기 시작함 -> S[0][0]을 뗄 때, S[1][0]을 뗄 때를 나누어서 점화식을 구현
• 항상 2 x n 배열로 스티커가 구성

---

풀이과정

예시를 통해 점화식을 생각해볼 수 있다. 스티커가 구성된 배열을 DP[2][5+1]라 하자.

편의 상 DP[0][0]과 DP[1][0]은 0으로 비워둔다.

그렇다면 DP[0][0] = DP[1][0] = 0으로 초기화를 하고, 나머지는 스티커 점수로 값을 채워야 한다.

0	50	10	100	20	40
0	30	50	70	10	60

 

DP[0][3]를 떼거나, DP[0][3]를 떼지 않으면 DP[1][3]를 뗄 수 있다.

DP[0][3]를 뗄 때 DP[0][0]을 선택할 때와 DP[1][0]을 선택할 때에 따라 경우가 나눈다.

DP[0][1]을 뗄 때 해당 인덱스에서 가능한 최대 점수를 표시하면 다음과 같다. 사용하지 못하는 스티커는 x로 표시했다.

0	50	x	100	20	40
0	x	50	x	10	60

DP[1][1]을 뗄 때 해당 인덱스에서 가능한 최대 점수를 표시하면 다음과 같다. 사용하지 못하는 스티커는 x로 표시했다.

0	x	x	100	20	40
0	30	x	x	10	60

따라서 위에 표시한 값을 토대로 DP[0][3]에서 점화식은 다음과 같다.

DP[0][3] = max(DP[1][2], DP[1][1]) + DP[0][3]

=> DP[0][i] = max(DP[1][i-1], DP[1][i-2]) + DP[0][i]

 

DP[1][3]를 뗄 때에도 DP[0][0]을 선택할 때와 DP[1][0]을 선택할 때에 따라 경우가 나눈다.

DP[0][1]을 뗄 때 해당 인덱스에서 가능한 최대 점수를 표시하면 다음과 같다. 사용하지 못하는 스티커는 x로 표시했다.

0	50	x	x	20	40
0	x	x	70	10	60

DP[1][1]을 뗄 때 해당 인덱스에서 가능한 최대 점수를 표시하면 다음과 같다. 사용하지 못하는 스티커는 x로 표시했다.

0	x	10	x	20	40
0	30	x	70	10	60

따라서 위에 표시한 값을 토대로 DP[1][3]에서 점화식은 다음과 같다.

DP[1][3] = max(DP[0][1], DP[0][2]) + DP[0][3]

=> DP[1][i] = max(DP[0][i-2], DP[0][i-1]) + DP[1][i]

 

따라서, 가능한 스티커 최대 점수는

result = max(DP[0][i], DP[1][i])

이다.

---

코드

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int T; // T: 테스트케이스 수, n: 스티커 수
    int DP[2][100001];

    scanf("%d", &T);

    for(int i=0; i<T; i++){
        int n;
        scanf("%d", &n);

        DP[0][0] = DP[1][0] = 0;

        for(int j=1; j<=n; j++)
            scanf("%d", &DP[0][j]);
        for(int j=1 ; j<=n; j++)
            scanf("%d", &DP[1][j]);

        for(int j=2; j<=n; j++){
            DP[0][j] = DP[0][j] + max(DP[1][j-1], DP[1][j-2]);
            DP[1][j] = DP[1][j] + max(DP[0][j-1], DP[0][j-2]);
        }

        printf("%d\n", max(DP[0][n], DP[1][n]));
    }

}

---

예제

---

결과