[백준 9465번] 스티커

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

9465번: 스티커

<문제 풀이> 다이나믹 프로그래밍

 

 

스티커를 위와 같이 2xN 배열로 표현했을 때 dp를 아래와 같이 정의할 수 있습니다.

 

dp[i][j] : 1열부터 j-1열까지 스티커를 떼어냈고 i행 j열에 있는 스티커를 떼어냈을 때 최솟값

 

N-1열까지 dp값이 잘 채워졌다고 가정하고 N열에 스티커를 뗄 수 있는 방법은 아래와 같은 4가지 경우의 수가 있습니다.

 

1. 1행 N열에 스티커를 떼어낼 때 2행 N-2열에 있는 스티커를 떼어낸 경우

2. 1행 N열에 스티커를 떼어낼 때 N-1열에 스티커를 아무것도 떼지 않은 경우

3. 2행 N열에 스티커를 떼어낼 때 1행 N-1열에 있는 스티커를 떼어낸 경우

4. 2행 N열에 스티커를 뗴어낼 때 N-1열에 스티커를 아무것도 떼지 않은 경우

N-1열에 아무것도 떼지 않는 경우는 N-2열에서 스티커를 떼어낸 경우입니다.

 

위 규칙들로 아래와 같은 dp 점화식을 만들 수 있습니다.

 

dp[1][1] = point[1][1];
dp[2][1] = point[2][1];
for (int i = 2; i <= n; i++) {
    dp[1][i] = max(dp[2][i - 1], dp[2][i - 2]) + point[1][i];
    dp[2][i] = max(dp[1][i - 1], dp[1][i - 2]) + point[2][i];
}
cout << max(dp[1][n], dp[2][n]) << '\n';

 

 

<C++소스코드>

#include<iostream>
#include<algorithm>
using namespace std;
 
int n;
int point[3][100001];
int dp[3][100001];
int main(){
    ios_base::sync_with_stdio(false);
 
    int T; cin >> T;
    while (T--) {
        fill(&dp[0][0], &dp[2][100001], 0);
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> point[1][i];
        }
        for (int i = 1; i <= n; i++) {
            cin >> point[2][i];
        }
        dp[1][1] = point[1][1];
        dp[2][1] = point[2][1];
        for (int i = 2; i <= n; i++) {
            dp[1][i] = max(dp[2][i - 1], dp[2][i - 2]) + point[1][i];
            dp[2][i] = max(dp[1][i - 1], dp[1][i - 2]) + point[2][i];
        }
        cout << max(dp[1][n], dp[2][n]) << '\n';
    }
    return 0;
}