[백준 BOJ][DP] 9465 스티커

9465_스티커

링크

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

 

풀이

 

 

만약 별에서 시작했다면 1이나 2를 갈 수 있습니다.

하지만 2는 1을 거쳤다 갈 수 있기 때문에 1로 가야합니다.

 

 

이 상황도 마찬가지로 1로 가는 게 이득입니다.

 

그렇다면 위에서 시작했던 밑에서 시작했던 대각선으로만 가는 게 최선의 방법일까요?

 

아닙니다. 반례를 들어보면,

 

이렇게 대각선으로만 가면 102라는 값이 나오지만 최적이 아니라는 것을 알 수 있습니다.

 

 

이렇게 두 칸 전에서 오는 값도 체크해줘야 합니다.

 

 

세 칸 전에서 오는 건 충분히 더 많은 구역을 거칠 수 있기 때문에 보지 않아도 됩니다.

 

DP[n][i]를 n번째 줄의 i번째까지 얻을 수 있는 최고의 점수라고 정의합니다. (n은 0~1, i는 1~100,000)

DP[0][1] = arr[0][1], DP[1][1] = arr[1][1]로 초기화 해줍니다.

 

i >= 2부터,

DP[0][i] = max(DP[1][i-1], DP[1][i-2]) + arr[0][i]

DP[1][i] = max(DP[0][i-1], DP[0][i-2]) + arr[1][i]

라는 점화식을 사용해줍니다.

 

그리고 max(DP[0][n], DP[1][n])을 출력해줍니다.

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

//9465_스티커 #include <cstdio> #include <algorithm> using namespace std;   int DP[2][100001], arr[2][100001], n, T;   int main() {     scanf("%d", &T);       while (T--) {         scanf("%d", &n);           for (int i = 0; i < 2; ++i) {             for (int j = 1; j <= n; ++j) {                 scanf("%d", &arr[i][j]);             }         }           DP[0][1] = arr[0][1], DP[1][1] = arr[1][1];           for (int i = 2; i <= n; ++i) {             DP[0][i] = max(DP[1][i - 1], DP[1][i - 2]) + arr[0][i];             DP[1][i] = max(DP[0][i - 1], DP[0][i - 2]) + arr[1][i];         }           printf("%d\n", max(DP[0][n], DP[1][n]));     }       return 0; } Colored by Color Scripter

cs