문제 링크

성능 요약

메모리: 14736 KB, 시간: 124 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 1월 8일 21:41:47

문제 설명

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

풀이

느낀점

• 이전에 풀었던 RGB거리 문제에서 조금 더 응용된 문제였다.
• 첫시도에서 잘못된 설계임을 알고 어렵다고 느꼈지만 포기하지 않고 스스로 다시 생각해낸 점이 뿌듯하다.

설계 : 60분

• R, G, B를 행으로 두고, 집의 수만큼 열을 둔다.
• 첫번째 설계에서는 각 칸에 {누적비용, 시작색}을 저장하도록 하여 지금 칠하려는 색과 다른 두가지 색상으로 이전 집이 칠해진 각각의 경우에서 최소값을 가져오도록 했다. → 시작색을 고려하지 않고 최소값만 넘겨 마지막에만 확인하니까 누락되는 최소값이 생김
• 두번째 설계에서는 dp[지금 칠할 색][지금 칠할 집][시작집 색] 으로 3차원 dp테이블을 구성했다.
• 이전 집의 지금 색과 다른 두가지 색상 경우에서 시작집 색에 따라 값이 있는 경우들만으로 최소비용을 갱신했다.

코드(Java)

• 구현 시간: 30분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: RGB거리 2_17404
 * Date: 2025.01.08
 */

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
        int[][] street = new int[3][n+1];
        for (int j = 1; j <= n; j++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 0; i < 3; i++) {
                street[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][][] dp = new int[3][n+1][3];
        for (int i = 0; i < 3; i++) dp[i][1][i] = street[i][1];

        for (int j = 2; j <= n; j++) {
            for (int i = 0; i < 3; i++) {
                for (int s = 0; s < 3; s++) {
                    int a = dp[(i+4)%3][j-1][s];
                    if (a == 0) a = 123456789;
                    int b = dp[(i+5)%3][j-1][s];
                    if (b == 0) b = 123456789;
                    dp[i][j][s] = Math.min(a, b) + street[i][j];
                }
            }
        }

        int answer = Integer.MAX_VALUE;
        for (int i = 0; i < 3; i++) {
            answer = Math.min(answer, Math.min(dp[i][n][(i+4)%3], dp[i][n][(i+5)%3]));
        }

        bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
		br.close();
	}
}