[알고리즘] 백준 1149번: RGB거리 (C++), 점화식...

'점화식을 어떻게 세울 것인가'가 큰 관건이었다. '큰 문제를 작은 문제로 나누자'라는 키워드는 이제 금방 떠오르고, 나눌 수 있었지만 이들이 어떤 관계를 갖는지는 알 수가 없었다.

 

R이면 G와 B 중에 하나를 골라야 하고, G이면 R과 B 중에 하나를 골라야 하는데 색을 고를 수 있는 경우가 3가지일 뿐인 더러 관계를 가질 수는 있긴 한 지가 의문이었다.

 

그래서 풀이를 보고, 다른 DP문제였던 2579번(계단 오르기)의 풀이를 보면서 느꼈지만 https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

작은 문제부터 큰 문제에 도달하면서 규칙성을 찾되 이 규칙성을 코드로 전환하는 과정과 그 관계에 있어서 확실한 이유가 무엇인지가 점점 필요하다고 느끼고 있다.

 

아직까지 DP 알고리즘에 있어서 초기 단계라고 생각한다. 더 풀어보아야 하며 관계성을 파악하는 능력과 이를 점화식으로 전환하는 능력까지 키워야 한다.

 

---

틀 벗어나기

늘 그렇게 느꼈지만 예를 들어 이분 탐색을 배울 때, 어느 정도 코드를 작성할 때 '구하려는 값이 이분 탐색으로 먹히는 것이 맞는지 low가 무엇인지 high가 어떤 값이어야 하는지 while문 안에서 논리가 정확한지'를 고민한다. 이 것이 나쁘다고 생각하진 않는다. 문제를 풀어가면서 생긴 '나만의 틀'이라 되려 문제를 풀 때의 프리셋이 형성되었다고 생각한다. 하지만 가끔은 같은 알고리즘에 불구하고, 틀을 벗어남을 요구한다. 이번 문제가 나에게 있어서는 그랬다.

>> 틀을 벗어남으로써 틀의 영역을 넓혀나가는 느낌으로 받아들여졌다.

 

이번 문제에서 풀이를 찾다가 cache배열에 저장하는 식이 3개(점화식)가 나와있는 것이 '나만의 틀'을 벗어났었다. 

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

int cache[1001][3] = { 0, };
int map[1001][3] = { 0, };

int main() {
	int n, answer;
	cin >> n;

	for (int i = 1; i <= n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		map[i][0] = a;
		map[i][1] = b;
		map[i][2] = c;
	}

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

	answer = min(min(cache[n][0], cache[n][1]), cache[n][2]);
	cout << answer;
	return 0;
}

맨 끝 집의 색깔이 R, G, B인 경우를 고려한다면 충분히 나올 수 있는 코드였다. 즉, 3가지 경우를 모두 점화식으로 전환할 수 있었어야 하는 것과 맞닿아있는 집들을 모두 다른 색으로 칠해야 한다는 것을 코드로 전환시킬 수 있는가를 묻는 문제였다.