[BOJ] 백준 9465번: 스티커

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

9465번: 스티커

이번에도 DP 기본 문제입니다.

 

#include <bits/stdc++.h>
using namespace std;

int T, n, score[3][100001], dp[100001][3];

void solve(){
	dp[1][0] = 0;
	dp[1][1] = score[1][1];
	dp[1][2] = score[2][1];
	
	for(int i = 2; i <= n; ++i){
		dp[i][0] = max(dp[i-1][1], dp[i-1][2]);
		dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + score[1][i];
		dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + score[2][i]; 
	}
	
	cout << max(dp[n][1], dp[n][2]) << '\n';
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> T;
	
	while(T--){
		cin >> n;
		for(int i = 1; i <= 2; ++i){
			for(int j = 1; j <= n; ++j){
				cin >> score[i][j];
			}
		}
		solve();
	}
}

 

이번에도 1) table 정의 2) 점화식 찾기 3) 초기값 설정의 3단계로 일관성 있게 구현했습니다.

 

1) table 정의 
dp[i][k] : i번째 열에서 k의 선택을 할 때 스티커 점수의 합의 최대값 
(k = 0 : 아무것도 안고름, k = 1 : 첫번째 행 스티커 고름, k = 2 : 두번째 행 스티커 고름)

2) 점화식 찾기
dp[i][0] = max(dp[i-1][1], dp[i-1][2]);  
dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + score[1][i];
dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + score[2][i];  

3) 초기값 설정
dp[1][0] = 0;
dp[1][1] = score[1][1];
dp[1][2] = score[2][1]; 

 

자교 문병로 교수님께서 쓰신 쉽게 배우는 알고리즘에 이와 비슷한 돌놓기 문제가 소개되어 있어 공부한 적이 있는데, case를 나눠서 풀이하는 방식이 직관적으로 다가와 쉽게 풀 수 있었습니다. 

 

살짝 고민했던 부분은 dp[i][0] = max(dp[i-1][1], dp[i-1][2]); 부분입니다. 

dp[i-1][0]까지도 비교를 해줘야하나 싶었는데 스티커 점수가 음이 아닌 정수이므로 스티커를 선택하는 dp[i-1][1] 또는 dp[i-1][2]가 스티커를 선택하지 않는 dp[i-1][0]보다 값이 클 수 밖에 없어 비교가 불필요합니다. 따라서 출력하는 값이  *max_element(dp[n], dp[n]+3) 이어도 올바른 답을 출력하지만, dp[n][0]은 항상 dp[n][1], dp[n][2]보다 작으므로 max(dp[n][1], dp[n][2]) 으로 충분한 것입니다.

 

경험상 어떤 제약이 있거나 추가 조건이 있을 때 1차원의 table로는 풀이하기 어려운 경우가 많은데 2차원, 3차원, 4차원 등으로 table의 차원을 늘려 이런 조건들을 처리해주면 유용했습니다.

 

시간복잡도는 O(n) 입니다.