[C++] 백준 9465번 - 스티커

---

0. 문제

 

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

 

1. 아이디어

 

1) 열을 기준으로 하나씩 늘려나가며 각 경우의 수에 대한 최댓값을 기록해둔다.

 

2) N번째 열에 선택될 수 있는 점수는, 1. N-1번째 열에서 스티커가 떼어지지 않았을 때, 2. N-1번째 열에서 위 스티커가 떼어졌을 때, 3. N-1번째 열에서 아래 스티커가 떼어졌을 때. 총 3가지의 경우로 나누어서 생각할 수 있다.

 

3) 그렇게 시작해서 1번째 열까지 범위를 넓혀오면 정답을 찾을 수 있다.

 

2. 소스코드

 

#include <iostream>
#include <algorithm>
const int MAX = 100000;
int N, value[2][MAX], dp[MAX][3];
//value 배열은 스티커의 점수를 저장
//dp 배열은 DP방식으로 문제를 풀기 위해 이전까지의 값들을 저장
 
int sticker(int c, int status) // top-down 방식으로 풀기 위한 재귀함수
{
    if (c == N) return 0; // 0열부터 N-1열까지가 유효
    if (dp[c][status] != -1) return dp[c][status];
    //dp[c][status]에 값이 있다는 것은 이전에 계산한 적이 있음!
    //ex) dp[3][1] 원소는 2열의 아래쪽 스티커가 떼어졌을 때, 3열부터 N-1열까지 얻을 수 있는 점수의 최댓값
 
    int result = sticker(c + 1, 0); // c번열에는 스티커가 떼어지지 않았다고 가정했을 때의 값을 우선 대입
    if (status != 1) result = std::max(result, sticker(c + 1, 1) + value[0][c]);
    if (status != 2) result = std::max(result, sticker(c + 1, 2) + value[1][c]);
 
    dp[c][status] = result;
    return result;
}
int main()
{
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    int T;
    std::cin >> T;
    for (int t = 0; t < T; t++)
    {
        std::cin >> N;
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < N; j++)
                std::cin >> value[i][j];
 
        for (int i = 0; i < N; i++)
            for (int j = 0; j < 3; j++)
                dp[i][j] = -1; // dp배열 초기화
        std::cout << sticker(0, 0)<<'\n';
    }
}

 

3. 결과

 

 

4. 피드백

 

• top-down 방식(즉, 재귀함수를 이용하는 방식)에 대해서 코드 이해가 힘들다.. 연습해보자!

• DP문제를 푸는데 있어서는, 고정된 값과 변하는 값을 잘 확인해서 메모이제이션 기법을 사용하자.

---