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

9465번: 스티커

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

주어진 조건에 따라 스티커를 선택할 때, 스티커 점수의 최댓값을 구하여라.

 

 스티커를 선택할 때의 조건은 다음과 같습니다.

선택한 스티커와 인접한(상, 하, 좌, 우) 스티커는 선택할 수 없다.

---

시간복잡도 어림하기

브루트 포스 알고리즘

 각 스티커는 선택하는지 선택하지 않는지의 두 가지 상태를 가질 수 있습니다. 실제로 스티커 선택 제한 조건에 의해 더 적은 수의 경우의 수를 가지지만, n의 최댓값은 100,000이고, 실제로 스티커는 2n개 있으므로 아주 큰 경우의 수가 나타날 것입니다. 만약, 줄어드는 경우의 수를 생각하여 2n의 반이나 1/1000로 산정해도 제한 시간내에 문제를 해결하기 어려운 수치입니다.

 

DP 알고리즘

 스티커 선택은 주변 스티커 선택의 영향을 받으므로 현재 값을 계산하기 위해 이전 계산 값을 이용할 수 있을 것이라 예측할 수 있습니다. 만약, 열을 기준으로 인덱스를 설정한다면 n번의 탐색으로 최적의 값을 계산할 수 있을 것입니다. 이는 제한 시간 내에 문제를 해결하기 적절한 수치이므로 DP를 사용하여 문제를 해결해봅시다.

---

알고리즘 설계하기

 스티커 선택은 할 열을 기준으로 최대 하나의 스티커만 선택할 수 있습니다. 이는 "선택한 스티커와 인접한 스티커는 선택할 수 없다."라는 조건 때문입니다. 따라서 한 열에서 얻을 수 있는 점수를 통해, 현재 인덱스 i까지 얻을 수 있는 최댓값을 dp[i]에 저장하겠습니다.

 

 dp[i] 값은 어떻게 계산할 수 있을까요? 그전에 한 열에서 스티커를 선택하는 경우의 수를 생각해봅시다. 스티커 선택의 경우의 수는 다음과 같습니다.

1. 위 스티커를 선택한다.
2. 아래 스티커를 선택한다.
3. 아무 스티커도 선택하지 않는다.

 이때, 1번 경우에는 이전 열에서 아래 스티커를 선택하거나 아무 스티커도 선택하지 않아야 하며, 2번 경우에는 이전 열에서 위 스티커를 선택하거나 아무 스티커도 선택하지 않아야 합니다.

 

 따라서, i에서 스티커 점수 최댓값을 계산하기 위해 '위 스티커 선택', '아래 스티커 선택', '아무 스티커도 선택하지 않음'의 세 상태로 나누어 최댓값을 각각 갱신할 것입니다. 각 상태에 대한 최댓값 알고리즘은 다음과 같을 것입니다.

1. 위 스티커를 선택하는 경우
 max(이전 열의 아래 스티커를 선택하는 경우, 이전 열에서 아무 스티커도 선택하지 않는 경우) + 위 스티커 점수

2. 아래 스티커를 선택하는 경우
 max(이전 열의 위 스티커를 선택하는 경우, 이전 열에서 아무 스티커도 선택하지 않는 경우) + 아래 스티커 점수

3. 아무 스티커도 선택하지 않는 경우
 이전 열에서 위 스티커, 아래 스티커, 아무 스티커도 선택하지 않는 경우의 수 중 최댓값

 이를 바탕으로 알고리즘을 구현하겠습니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

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

int t, n, dp[100004][3];
int main(){
	/*입출력 성능 향상*/
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> t;
    while(t--){
    	/*매 테스트 마다 dp 초기화*/
        memset(dp, 0, sizeof(dp));
        cin >> n;
        for(int i = 0; i < 2; i++){
            for(int j = 0; j < n; j++) cin >> dp[j][i]; //dp에 바로 스티커 점수 초기화
        }
        
        for(int i = 1; i < n; i++){
            dp[i][0] += max(dp[i - 1][1], dp[i - 1][2]); //위 스티커 선택
            dp[i][1] += max(dp[i - 1][0], dp[i - 1][2]); //아래 스티커 선택
            dp[i][2] = max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][2])); //아무 스티커도 선택하지 않음
        }
        cout << max(dp[n - 1][0], max(dp[n - 1][1], dp[n - 1][2])) << '\n';
    }
    return 0;
}

 dp배열에서 [i][0]은 i열에서 위 스티커를 선택하는 경우, [i][1]은 아래,  [i][2]는 아무 스티커도 선택하지 않는 경우를 의미합니다.

 해당 코드에서는 입력을 받을 때, 바로 dp 배열에 값을 저장했는데, 이와 같이 구현한 이유는 dp값을 갱신할 때, 반드시 이전 열만의 값만 조회하고, 한 번 정해진 값은 다시 갱신되지 않기 때문입니다.

 

 여기서 가장 중요한 부분은 매 테스트 케이스마다 dp배열을 초기화 해주는 것입니다. 매 테스트 케이스 마다 독립적으로 실행해야 하므로 <string> 헤더의 memset 함수를 통해 dp 배열을 0으로 초기화 했습니다. 

---