3장 다이나믹 프로그래밍 - (3) 문제 풀이 4 [9465번 - 스티커]

1. 문제 설명

n번째 열의 스티커를 뗀 상태를 정의하였다.

n번째 열 1행, 2행 모두 떼지 않은 경우의 상태를 0

1행만 뗀 경우의 상태를 1

2행만 뗀 경우의 상태를 2라고 정의하였다.

d[s][n] : n번째 열의 상태가 s 일 때 최고 점수 

p0 : 1행의 점수를 저장한 배열

p1 : 2행의 점수를 저장한 배열 

d[0][n] = max(d[0][n-1], d[1][n-1], d[2][n-2])

d[1][n] = max(d[0][n-1], d[2][n-1])+p0[n]

d[2][n] = max(d[0][n-1], d[1][n-1])+p1[n]

정답 : max(d[0][n],d[1][n],d[2][n])

2. 소스 코드

#include <iostream>

#include <algorithm>

using namespace std;

int d[3][100001];

int p0[100001];

int p1[100001];

int main(void) {

int test_case;

cin >> test_case;

while (test_case--) {

int n;

cin >> n;

for (int i = 1; i <= n; i++) {

cin >> p0[i];

}

for (int i = 1; i <= n; i++) {

cin >> p1[i];

}

d[0][1] = 0;

d[1][1] = p0[1];

d[2][1] = p1[1];

for (int i = 2; i <= n; i++) {

d[0][i] = max(max(d[0][i - 1], d[1][i - 1]), d[2][i - 1]);

d[1][i] = max(d[0][i - 1], d[2][i - 1]) + p0[i];

d[2][i] = max(d[0][i - 1], d[1][i - 1]) + p1[i];

}

int result = max(max(d[0][n], d[1][n]), d[2][n]);

cout << result << endl;

}

return 0;

}