[알고리즘] 백준 9465번: 스티커 (C++), 논리와 직관 그 어디쯤 사이에

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

9465번: 스티커

이번 문제는 TC를 보고 나서 점화식을 어떻게 짜야할지 혼란을 가져다주는 문제였다.

하지만, TC를 간단하게 생각해보면 쉽게 풀 수 있었다.

---

솔루션에 도달하는 과정

5
50 10 100 20 40
30 50 70 10 60

다음 TC가 문제를 다시 생각해보게 했었다. 그 전의 코드는 이렇다.

#include <iostream>
#include <cmath>
using namespace std;

int T;
int cache[2][100001] = { 0, };
int map[2][100001] = { 0, };

int main() {
	cin >> T;
	for (int t = 0; t < T; t++) {
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> map[0][i];
		}
		for (int i = 1; i <= n; i++) {
			cin >> map[1][i];
		}

		for (int i = 1; i <= n; i++) {
			cache[0][i] = cache[1][i - 1] + map[0][i];
			cache[1][i] = cache[0][i - 1] + map[1][i];
		}

		cout << max(cache[0][n], cache[1][n]) << '\n';
	}
	return 0;
}

무조건 대각선 방향의 스티커를 더해주는 것이 정답이겠거니 했지만 올린 TC 같은 경우엔 한 칸 더 뒤에 있는 대각선을 택하게 된다.

---

솔루션에 도달하는 과정 (2)

value와 value2 중에 더 큰 값을 선택하면 된다.

그렇다면 여기서 이런 말이 나올 수 있다. '3칸 뒤의 값도 더 큰 값을 가지고 있을 수 있는데 왜 안 따지는가?'

그에 대한 답은 3칸 뒤에 값을 따질 필요 없이 value를 거쳐 대각선 2개를 더 거치면 value3에 도달할 수 있고, 값 2개를 더 더했으므로 더 큰 값을 초래하기 때문이라는 이유가 답이 된다.

 

그래서 점화식에서는 두 칸 전의 값까지만 따져주면서 점화식을 도출해내면 된다.

---

[AC 코드]

#include <iostream>
#include <cmath>
using namespace std;

int T;
int cache[2][100001] = { 0, };
int map[2][100001] = { 0, };

int main() {
	cin >> T;
	for (int t = 0; t < T; t++) {
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> map[0][i];
		}
		for (int i = 1; i <= n; i++) {
			cin >> map[1][i];
		}

		for (int i = 1; i <= n; i++) {
			cache[0][i] = max(cache[1][i - 1], cache[1][i - 2]) + map[0][i];
			cache[1][i] = max(cache[0][i - 1], cache[0][i - 2]) + map[1][i];
		}

		cout << max(cache[0][n], cache[1][n]) << '\n';
	}
	return 0;
}