DP문제에 전형적인 풀이 방법인 메모제이션을 이용하여 문제를 풀었다.
처음에는 어떤 식으로 문제를 풀어 나가야 할지 감이 잡히지 않았다.
계속 생각한 결과 한가지만 주의하면 된다는 생각을 하게 되었다. 이웃한 집만 같은 색깔이 아니면 되기 때문에 하나의 집을 임의의 색으로 칠하면 다음 집에서는 선택할 수 있는 경우가 2가지로 좁혀지고, 그다음은 여전히 2가지의 선택의 경우가 생긴다. 즉, 소모 값들을 배열에 저장한다 생각하면, 같은 column에 있는 값만 선택하지 않으면 된다.
그렇다면 이제 index문제만 해결하면 문제는 풀린다.
R은 [0]에, G는 [1]에, B는 [2]에 저장한다 하자. 2번 index의 요소를 처리한다 했을때, 0과 1에 접근할 수 있는 방법을 찾으면 된다.
링 버퍼의 개념을 이용했다. 어떠한 index이던지 1과 2를 더한 뒤, 3으로 나머지 연산을 처리하게 되면 자신을 제외한 색에 접근할 수 있다.
그리고 그 소모 값들 중, 작은 값들을 선택해 쌓아 나가면 결국 답을 저장하는 배열 마지막 row에 최종 값들이 저장되고,
그 수 중 가장 작은 값을 택하면 된다.
다음은 Java로 작성한 코드이다.
import java.util.Scanner;
public class RGB {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[][] map = new int[n][3];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 3; j++) {
map[i][j] = scan.nextInt();
}
}
int[][] solution = new int[n][3];
solution[0][0] = map[0][0];
solution[0][1] = map[0][1];
solution[0][2] = map[0][2];
for (int i = 1; i < n; i++) {
for (int j = 0; j < 3; j++) {
solution[i][j] = map[i][j] + Math.min(solution[i-1][(j+1)%3],solution[i-1][(j+2)%3]);
}
}
int min = 1000*n;
for (int i = 0; i < 3; i++) {
min = Math.min(solution[n-1][i],min);
}
System.out.print(min);
}
}
