9465번: 스티커
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의
www.acmicpc.net
1. 문제 설명
예제 입력 1에서 첫 번째 테스트 케이스는 문제 속 예시와 동일하고, 두 번째 테스트 케이스는 하늘색 박스를 친 스티커를 골랐을 때가 점수가 최대가 된다.
2. 구현 아이디어
처음 봤을 때 백준 1149번: RGB 거리와 비슷하게 풀면 될 것 같다는 생각이 들었다.
그래서 점화식을 아래와 같이 세웠다.
🍙 점화식
dp[0][i] = dp[1][i-1] + board[0][i]
dp[1][i] = dp[0][i-1] + board[1][i]
직전에 0번째 행의 스티커를 고르게 된다면 변이 겹치기 때문에 이번 차례에서는 0번째 행의 스티커를 고르지 못한다.
그러므로 dp[0][i]는 직전에 1번째 행의 스티커를 고르고, 이번에는 0번째 위치의 스티커를 골랐을 때를 의미하게 된다.
직전에 1번째 행의 스티커를 골랐을 때도 마찬가지이다.
하지만 위와 같이 점화식을 세우고 IDE에서 값을 출력해본 결과 예제 출력과 다르게 나왔다.
점화식이 틀린 이유는 문제에서 확인할 수 있었다.
문제 속 예시를 보면 3번째 열에서 100을 고르고, ✨4번째 열에서는 아무것도 고르지 않고✨, 5번째 열에서 60을 고른 모습을 확인할 수 있다.
직전에 0번째 행을 고르고 이번 순서에 1번째 행을 고르는 것보다 전전 차례에서 더 큰 수를 고르고, 직전에는 고르지 않고, 이번 순서에서 1번째 행을 고르는 것이 더 큰 경우도 있다.
이렇게 될 경우 스티커끼리 변을 공유하지 않기 때문에 이번 차례가 0번째 행이든, 1번째 행이든 상관없이 전전 차례에서는 아무거나 고를 수 있다.
이를 참고하여 점화식을 아래와 같이 변경하였다.
🍙 점화식
dp[0][i] = max(dp[1][i-1] + board[0][i], max(dp[0][i-2], dp[1][i-2]) + board[0][i])
dp[1][i] = max(dp[0][i-1] + board[1][i], max(dp[0][i-2], dp[1][i-2]) + board[1][i])
3. 전체 코드
#include <bits/stdc++.h>
using namespace std;
int t;
int n;
int board[2][100000];
int dp[2][100000];
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> t;
while (t--) {
// 입력
cin >> n;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < n; ++j) {
cin >> board[i][j];
}
}
// DP 배열 초기화
memset(dp, 0, sizeof(dp));
dp[0][0] = board[0][0];
dp[1][0] = board[1][0];
dp[0][1] = dp[1][0] + board[0][1];
dp[1][1] = dp[0][0] + board[1][1];
// DP 진행
for (int i = 2; i < n; ++i) {
dp[0][i] = max(dp[1][i-1] + board[0][i], max(dp[0][i-2], dp[1][i-2]) + board[0][i]);
dp[1][i] = max(dp[0][i-1] + board[1][i], max(dp[0][i-2], dp[1][i-2]) + board[1][i]);
}
cout << max(dp[0][n-1], dp[1][n-1]) << "\n";
}
return 0;
}
점화식을 그대로 코드로 옮겨주면 되고, 마지막에 0번째 행과 1번째 행 중 더 큰 값을 출력하여 최종적인 스티커 점수의 최댓값을 구할 수 있다.
