[BOJ] 9465번: 스티커

9465번: 스티커

해법

처음 내가 접근했던 방법은 그냥 무식하게 대각선으로만 생각하고 풀었다. 그래서 당연히 틀렸고 친구와 다른 분들의 도움을 받아서 이 문제를 풀게 됐다. 우선 이 문제는 DP이고 DP식은 dp[i][j]: i열,j행까지의 스티커의 최대값이다.

하나를 선택하면 상하좌우를 선택하지 못하기 때문에 기본적으로 이동은 대각선으로만 가능하다.

그래서 DP식을 대각선쪽만 생각해서 짜면 절대 안된다. 

이렇게 한다면 250이 최대가 되어서 정답인 260이 아니게 된다.

즉 한 칸을 건너뛰어야 한다. 그러면 두 칸을 건너뛰는 것은 어떨까..? 결론부터 말하자면 손해다. 두 칸을 뛰게 되면 한 칸씩 대각선 건너는 것과 같은 지점을 가지만 거치는 것은 더 적으므로 항상 손해일 수 밖에 없다.

그래서 점화식을 다음과 같이 세울 수 있다.

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

기저 사례

dp[0][0] = A[0][0];
dp[1][0] = A[1][0];
dp[0][1] = dp[1][0] + A[0][1];
dp[1][1] = dp[0][0] + A[1][1];

전체 코드

#include <cstdio>
#include <algorithm>
using namespace std;

int dp[2][100001], A[2][100001];

int main()
{
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < n; ++j)
                scanf("%d", &A[i][j]);

        dp[0][0] = A[0][0];
        dp[1][0] = A[1][0];
        dp[0][1] = dp[1][0] + A[0][1];
        dp[1][1] = dp[0][0] + A[1][1];
        for (int i = 2; i < n; ++i) {
            dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + A[0][i];
            dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + A[1][i];
        }

        printf("%d\n", max(dp[0][n - 1], dp[1][n - 1]));
    }
    return 0;
}

 

느낀점

느낀점은 "문제를 잘 읽자, 그리고 많은 문제를 풀어서 경험을 쌓자"입니다.