[백준/c++] 9465번: 스티커

 

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

9465번: 스티커

 

2xn 스티커가 있고, 각 스티커에는 숫자가 적혀있다. 해당 스티커를 떼면 그 숫자를 얻을 수 있다. 숫자의 합이 최대가 되도록 스티커를 떼어내야 한다. 뗄 수 있는 스티커의 점수의 최댓값을 출력해라. 여기서 뗀 스티커의 상하좌우로 붙은 스티커는 뗄 수 없다.

2xn스티커이므로 2xi 스티커라고 가정하고 하나씩 차례대로 최댓값을 구해보자.

 

dp[i][0] = i열의 0행 스티커를 떼어냈을 경우

dp [i][1] = i열의 1행 스티커를 떼어냈을 경우

 

dp [2][0] = 30 + 10

dp [2][1] =  50 + 50

dp [3][0] = 50 + 50 + 100 or 30 + 100

dp [3][1] = 30 + 10 + 70 or 50 + 70

 

점화식 구하기

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

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

 

 

#include <iostream>
#include <algorithm>
#define num 100002
using namespace std;
int t, n, sticker[num][2];
long long dp[num][2];

void input(){
    cin >> n;
    for(int i=0; i<2; i++) for(int j=1; j<=n; j++) cin >> dp[j][i];
}

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

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--){
        input();
        solution();
    }
    return 0;
}

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!