[백준9465] 스티커 (C++)

BOJ 바로가기

#include <iostream>
#include<algorithm>
using namespace std;
int a[3][100001];
int d[3][100001];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		for (int i = 1; i <= 2; i++) {
			for (int j = 1; j <= n; j++)
				cin >> a[i][j];
		}
		d[0][0] = 0; d[1][0] = 0; d[2][0] = 0;
		for (int k = 1; k <= n; k++) {
			d[0][k] = max({ d[0][k - 1], d[1][k - 1], d[2][k - 1] });
			d[1][k] = max(d[0][k - 1], d[2][k - 1]) + a[1][k];
			d[2][k] = max(d[0][k - 1], d[1][k - 1]) + a[2][k];
		}
		cout << max({ d[0][n], d[1][n], d[2][n] }) << '\n';
	}
	return 0;
}

재귀함수를 이용한 TOP-DOWN 방식을 적용했을 땐 시간초과가 났다. 질문답변 글을 읽어보니, dp[3][100001]을 0으로 초기화했을 때 메모이제이션이 작동하지 않는 경우가 생기기 때문이라고 한다. 이 부분에 대해선 내일 다시 공부해봐야겠다.

📌아이디어

d[0][k]는 k번째에서 스티커를 떼지 않을 경우, d[1][k]는 위쪽 스티커 한 장을 뗄 경우, d[2][k]는 아래쪽 스티커 한 장을 뗄 경우의 최대 점수를 저장한 배열이다.

인접한 스티커를 떼면 안 된다는 조건이 있으므로, d[1][k]는 d[0][k] 또는 d[2][k]의 최댓값에 a[1][k]를 더해주면 된다. d[2][k]의 경우도 마찬가지이다. d[0][k]의 경우 스티커를 떼지 않은 상태이므로 d[0][k-1], d[1][k-1], d[2][k-2] 중에서 최댓값을 가진다.