[Algorithm] Baekjoon 9465번 : 스티커

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

9465번: 스티커

int arr[2][100002] = { 0 };
int dp[2][100002] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t = 0;
    int n = 0;
    int input = 0;
    vector<int> results;
 
    cin >> t;
 
    for (int i = 0; i < t; i++)
    {
        cin >> n;
 
        for (int j = 0; j < 2; j++)
        {
            for (int k = 2; k <= n + 1; k++)
            {
                cin >> arr[j][k];
            }
        }
 
        for (int col = 2; col <= n + 1; col++)
        {
            dp[0][col] = max(dp[1][col - 1], dp[1][col - 2]) + arr[0][col];
            dp[1][col] = max(dp[0][col - 1], dp[0][col - 2]) + arr[1][col];
        }
 
        results.push_back(max(dp[0][n + 1], dp[1][n + 1]));
    }
 
    for (auto& temp : results)
    {
        printf("%d\n", temp);
    }
}

규칙을 잘 찾아야하는 DP문제.

선택한 스티커의 변이 맞닿은 상,하,좌,우에 위치한 스티커는 선택할 수 없다.

해당 규칙을 지키면서 최대값을 구하는 문제이다.

 

기본적으로 bottom->top으로 값을 갱신하는데, 해당 위치의 dp값이 최고값이 되려면 그 이전에 선택할 수 있는 경우의 수를 구해야한다.

일단 기본적으로 바로 이전 열의 대각선위치의 스티커(row-1,col-1)를 선택지에 넣을 수 있다.

그러나, 이전 열의 대각선위치의 스티커보다 한 열 더 왼쪽의 스티커가 값이 굉장히 클 수 있다.

즉, col-1의 dp값을 버리면서까지 col-2의 dp값을 선택하는 경우가 존재한다는 것이다.

뭐 col-1의 dp값이 굉장히 작고, col-2값이 굉장히 크다면 충분히 col-1을 버리면서까지 선택해야한다.

같은행의 col-2의 dp값 같은 경우, 이미 col-1에 포함되어있을 수 있기 때문에 고려하지 않는다.