백준 9465 : 스티커

문제 링크입니다 https://www.acmicpc.net/problem/9465

9465번: 스티커

2행 N열로 배치되어 있는 스티커 점수 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 찾는 문제였습니다. 점화식을 세우기 위해 "D[N][K] : 길이가 N이고 마지막에 선택한 행이 K행인 스티커 점수의 최댓값"이라 한다면,

 

[1] K가 0일 때

→ K가 있는 열을 N열이라 했을 때, (1행, N-1열)의 스티커를 선택하는 경우와 (1행, N-2열)의 스티커를 선택하는 경우로 나누어서 생각할 수 있습니다. 두 경우를 제외하고는 최댓값이 될 수 없습니다(점수는 0보다 크거나 같기 때문).

 

[2] K가 1일 때

→ K가 있는 열을 N열이라 했을 때, (0행, N-1열)의 스티커를 선택하는 경우와 (0행, N-2열)의 스티커를 선택하는 경우로 나누어서 생각할 수 있습니다. 두 경우를 제외하고는 최댓값이 될 수 없습니다(점수는 0보다 크거나 같기 때문).

 

즉, 다음과 같은 점화식을 얻게 됩니다.

[1] D[N][0] = MAX(K가 있는 칸의 점수 + D[N-1][1], K가 있는 칸의 점수 + D[N-2][1])

→ K가 있는 칸의 점수 + 길이가 N-1인 스티커의 마지막에 1행을 선택한 경우 점수의 최댓값

→ K가 있는 칸의 점수 + 길이가 N-2인 스티커의 마지막에 1행을 선택한 경우 점수의 최댓값 중에서 최댓값

 

[2] D[N][1] = MAX(K가 있는 칸의 점수 + D[N-1][0], K가 있는 칸의 점수 + D[N-2][0])

→ K가 있는 칸의 점수 + 길이가 N-1인 스티커의 마지막에 0행을 선택한 경우 점수의 최댓값

→ K가 있는 칸의 점수 + 길이가 N-2인 스티커의 마지막에 0행을 선택한 경우 점수의 최댓값 중에서 최댓값

 

 

[소스코드]

 

#include<algorithm>
#include<cstdio>
using namespace std;
const int MAX = 100000 + 10;
 
//      map : 스티커를 입력 받을 배열
// dp[n][k] : 길이가 n이고 마지막에 선택한 스티커가 k행일 때 점수의 최댓값
int tc, n, map[2][MAX], dp[MAX][2];
 
int main(void) {
 
    scanf("%d", &tc);
 
    for (int t = 0; t < tc; t++) {
 
        scanf("%d", &n);
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &map[i][j]);
 
        // 2 x 1 스티커는 0행의 값, 1행의 값 두 가지 경우입니다
        dp[1][0] = map[0][0], dp[1][1] = map[1][0];
        
        // 길이가 2부터 n까지의 스티커 점수의 최댓값을 결정합니다
        for (int i = 2; i <= n; i++) {
 
            // 마지막에 선택하는 행은 0 또는 1 입니다
            for (int j = 0; j < 2; j++) {
 
                // 0행을 선택했다면 [1]의 경우
                if (j == 0) {
                    
                    // [1]
                    dp[i][j] = 
                        max(map[j][i - 1] + dp[i - 1][1], map[j][i - 1] + dp[i - 2][1]);
                }
                // 1행을 선택했다면 [2]의 경우
                else {
                    
                    // [2]
                    dp[i][j] = 
                        max(map[j][i - 1] + dp[i - 1][0], map[j][i - 1] + dp[i - 2][0]);
                }
            }
        }
        // 길이가 n인 스티커의 마지막에 0행을 선택하는 경우
        // 길이가 n인 스티커의 마지막에 1행을 선택하는 경우 중 최댓값
        printf("%d\n", max(dp[n][0], dp[n][1]));
    }
    return 0;
}