BOJ_1149 : RGB거리

👉 문제링크

1149번: RGB거리

---

---

🔸 문제 분석 🔸

• N개의 집에 R,G,B 3가지 색이 연속하지 않도록 칠한다.
  • 각 집의 세 가지 색에 대한 비용이 주어진다.
  • 모든 집을 칠하는 최소비용을 출력한다.
• 칠하는 경우의 수를 구하면 3x2x2x...x2 = 3x2x(n-1) = 6(n-1)
  • n은 최대 1,000이므로, 칠하는 경우의 수는 최대 5994가지
  • 가지수가 많지 않아 재귀, 백트래킹을 사용한 브루트 포스도 가능할 것 같지만, 시간은 0.5초이므로 DB를 이용한다.
• DP
  • 현재 위치에 3가지 색 별 최소값 누적 : 2차원 배열 dp[N][3]
  • 이전 값 중 현재 색과 다른 두 색 중 최소값 사용
  • 점화식 (now는 현재 인덱스, a는 현재 비용)
    • dp[now][0] = Math.min(dp[now-1][1], dp[now-1][2])+a[0]
    • dp[now][1] = Math.min(dp[now-1][0], dp[now-1][2])+a[1]
    • dp[now][2] = Math.min(dp[now-1][1], dp[now-1][0])+a[2]

🔸 코드 🔸

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = null;

        int N = Integer.parseInt(br.readLine());

        int[][] dp = new int[N + 1][3];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + Integer.parseInt(st.nextToken());
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + Integer.parseInt(st.nextToken());
            dp[i][2] = Math.min(dp[i - 1][1], dp[i - 1][0]) + Integer.parseInt(st.nextToken());
        }

        bw.write(Integer.toString(Math.min(Math.min(dp[N][0], dp[N][1]), dp[N][2])));
        bw.flush();
    }
}

🔸 코드 해석 🔸

• 1부터 N번째 집으로 R,G,B 각 색을 칠했을 때 최소값을 누적해간다.

---

🔸 end 🔸

• 전형적인 DP 문제인 것 같아 쉽게 풀이할 수 있었다.
• 문제 분석과 풀이 계획을 적어가며 풀었는데, 브루트 포스의 시간 계산이 미흡했던 것 같다.
  • 삼성 SW 역량 테스트 B형을 준비하는데, 이런 연산 수 계산에 대한 연습을 더 철저히 해야할 것 같다.