[어려워요알고리즘] BOJ 9465 : 스티커

Info

---

• 백준 9465번 스티커
• Silver 2 solved.ac
• 다이나믹 프로그래밍

Write UP

---

수학을 못 해서 그런지 DP 문제들이 너무 어렵네요..

점화식 세우는 법이랑 효율적인 탐색하는 방법을 많이 연습해야 할 것 같습니다.

사실 상하좌우 탐색이랑 최댓값 보고 BFS 돌리면 되겠네!! 했는데
케이스가 100,000개 / 제한시간이 1초라 시간초과가 뜰 것 같아서 DP로 접근을 했어요.

우선 각 좌표마다 값을 저장할 수 있도록 dp 배열을 선언했습니다.

이제 조건을 살펴봐야 하는데, 상하좌우론 이동이 안되니깐 대각선 방향만 선택할 수 있어요.

단!! 무조건 대각선이면 다 되는 것이 아니고 한 칸 건너 뛴 대각선을 선택하는 경우도 있다는 것이 함정입니다.

현재를 V라고 하고, 갈 수 있는 곳을 O라고 표현해보면,

idx	0	1	2	3
0	V	X
1	X	O	O

이렇게 되는거죠.

갈 수 있는 두 곳중 큰 값이 있는 곳으로 가야 최댓값이 만들어집니다.

여기서 세 칸 이상 떨어진 대각선과 같은 행의 두 칸 떨어진 곳을 고려하지 않는 이유는
탐색을 진행하면서 무조건 갈 수 있는 곳이기 때문이에요.

현재 위치에서 대각선으로 두 칸 떨어진 곳은 "갈림길"이기 때문에 선택을 하지 않으면 못 가지만

다른 곳은 노드를 거쳐거쳐 갈 수 있기 때문에 조건에서 제외됩니다.

우선 dp 배열을 초기화할께요.

dp[i][j] = arr[i][j - 1]을 선택했을 때의 최댓값

이걸 기억하고 시작합시다.

처음에 arr[0][0], arr[1][0], arr[0][1], arr[0][1]을 선택할 수 있기 때문에 아래와 같이 설정했습니다.

idx	0	1	2	3...
0	0	arr[0][0]	0	0
1	0	arr[1][0]	0	0

dp[0][2] 인 경우를 볼게요.
max(dp[1][0], dp[1][1])의 값을 넣어주면 됩니다.

dp[1][2] 면 max(dp[0][0], dp[0][1])의 값을 넣어주면 돼요.

이런 식으로 코드를 이어나가면 맨 마지막 노드에서 최댓값을 구할 수 있습니다.

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

int T, n;
int arr[2][100001];
int dp[2][100002] = { 0 };

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    scanf("%d", &T);
    
    for (int i = 0; i < T; i++) {
        scanf("%d", &n);
        
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < n; k++) {
                scanf("%d", &arr[j][k]);
            }
        }
        
        dp[0][0] = 0;
        dp[1][0] = 0;
        dp[0][1] = arr[0][0];
        dp[1][1] = arr[1][0];
        
        for (int j = 2; j <= n; j++) {
            dp[0][j] = arr[0][j - 1] + max(dp[1][j - 2], dp[1][j - 1]);
            dp[1][j] = arr[1][j - 1] + max(dp[0][j - 1], dp[0][j - 2]);
        }
        
        printf("%d\n", max(dp[0][n], dp[1][n]));
    }
}