[algorithm] 백준 - 스티커

 

DP 문제이다.

 

점수가 매겨진 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 점수에 합산될 수 없다.

 

스티커는 2*N으로 배치되어있다.

 

예를 들어 이런 스티커가 있다고 가정해보자.

50	10	100	20	40
30	50	70	10	60

이런 방향과

이런 방향으로 합산을 할 수 있다.

즉 대각선방향 값과 대각선방향으로 앞에 첫번째 쪽 값의 합산 중 가장 큰 것을 비교해서 계산하면 된다.

두번째 세번째 앞의 값은 계산할 필요가 없다. 그 이유는 

이런 식으로 계산이 되기 때문이다.

그렇기 때문에 대각선 방향에 위치한 값, 대각선 방향의 인덱스 - 1 에 위치한 값 중 큰 것으로 선택하면 된다.

 

점수를 차례차례 합산하여 최댓값을 계산해보면,

50	40	200	140	250
30	100	120	210	260

따라서 260을 구할 수 있다.

 

코드는 이렇게 나타낼 수 있다.

// 스티커
#include <iostream>
using namespace std;

int main(void){
    int test, num,dp[2][100001];
    cin >> test;
    while(test--){
        cin >> num;
        dp[0][0] = 0; dp[1][0] = 0;
        for(int i = 0; i < 2; i++){
            for(int j = 1; j <= num; j++){
                cin >> dp[i][j];
            }
        }
        for(int i = 2; i <= num; i++){
            dp[0][i] = max(dp[0][i] + dp[1][i - 1],dp[0][i] + dp[1][i - 2]);
            dp[1][i] = max(dp[1][i]+ dp[0][i - 1], dp[1][i] + dp[0][i - 2]);
        }
        cout << max(dp[0][num], dp[1][num]) << "\n";
    }
}