백준저지 9465번 스티커 문제 풀이

백준저지 9465번 스티커 문제입니다.

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

9465번: 스티커

 

다이나믹 프로그래밍 기초 문제입니다.

 

스티커가 가로 2줄로 이루어져 있고, 하나를 때면 인접한 스티커를 고를 수 없게 됩니다.

최근에 위를 골랏느냐, 아래를 골랐느냐에 따라서 다음 고를 수 있는 상태가 바뀌게 되므로, 2차원 DP 배열로 풀 수 있습니다.

 

 

DP 식은

 

dp[x][status] -> x번째 열 이후 스티커를 다 처리했고, 해당 열의 스티커의 상태가 status가 되었을 때 최대 가치

 

대충 이러한 정의가 될 것입니다.

 

자세한 내용은 코드를 첨부합니다.

 

#include <bits/stdc++.h>
using namespace std;

#define UP      0 //arr에선 위에위치, dp에선 위에것만 선택 가능할 시
#define DOWN    1
#define BOTH    2


int dp[100000][3]; //시작 x좌표와 선택할 수 있는 상태
int arr[100000][2];
int n;
int solve(int len, int stat) {
    if (len < 0 or len >= n or stat < 0 or stat >= 3) return 0;
    if (dp[len][stat] != -1) return dp[len][stat];
    int ans = 0;
    if (stat != DOWN) { //위에걸 선택할 수 있는 상태이면(UP or BOTH)
        ans = max(ans, arr[len][UP] + solve(len+1, DOWN)); //위에걸 선택
        ans = max(ans, solve(len+1, BOTH)); //그냥 안선택
    }
    if (stat != UP) { //아래걸 선택할 수 있는 상태이면(DOWN or BOTH)
        ans = max(ans, arr[len][DOWN] + solve(len+1, UP)); //위에걸 선택
        ans = max(ans, solve(len+1, BOTH)); //그냥 안선택
    }
    return dp[len][stat] = ans;
}
int main() {
    int t;
    cin >> t;
    while(t--) {
        
        cin >> n;
        for (int i=0; i < n; i++) {
            cin >> arr[i][UP];
        }
        for (int i=0; i < n; i++) {
            cin >> arr[i][DOWN];
        }
        memset(dp, -1, sizeof(dp));
        cout << solve(0, BOTH) << '\n';
    }
	return 0;
}