EunSung.log

RGB 거리

3 min read

문제 정보

풀이

다음 규칙을 만족하면서 모든 집을 칠하는 최소 비용을 구하는 문제다.

  • 1번 집의 색 2번 집의 색
  • N번 집의 색 N - 1번 집의 색
  • i번 집의 색 i - 1번 집의 색 & i번 집의 색 i + 1번 집의 색
  • ⇒ 한 마디로, 이웃한 집과 색이 달라야 한다.

dp 배열을 다음과 같이 정의한다.

  • dp[i][c]: i번째 집을 색 c로 칠했을 때의 최소 비용

i번째 집을 빨강으로 칠하려면 i - 1번째 집은 초록 또는 파랑이어야 하므로, 점화식은 다음과 같다.

  • dp[i][r] = cost[i][r] + min(dp[i-1][g], dp[i-1][b])
  • dp[i][g] = cost[i][g] + min(dp[i-1][r], dp[i-1][b])
  • dp[i][b] = cost[i][b] + min(dp[i-1][r], dp[i-1][g])

최종 답은 min(dp[n][r], dp[n][g], dp[n][b])다.

다만 실제 구현에서는, 현재 값을 구하는 데 바로 직전 값만 필요하므로 2차원 배열 대신 변수 3개(prevR, prevG, prevB)로 구현했다.

코드

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int prevR = Integer.parseInt(st.nextToken());
        int prevG = Integer.parseInt(st.nextToken());
        int prevB = Integer.parseInt(st.nextToken());
        
        for (int i = 1; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            
            int red = Integer.parseInt(st.nextToken());
            int green = Integer.parseInt(st.nextToken());
            int blue = Integer.parseInt(st.nextToken());
            
            // i번째 집을 각 색으로 칠할 때의 최소 비용
            int curR = red + Math.min(prevG, prevB);
            int curG = green + Math.min(prevR, prevB);
            int curB = blue + Math.min(prevR, prevG);
            
            prevR = curR;
            prevG = curG;
            prevB = curB;
        }
        
        int answer = Math.min(prevR, Math.min(prevG, prevB));
        
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        bw.write(answer + "\n");
        bw.flush();
        bw.close();            
    }
}

관련 노트

  • 20260123 땅따먹기: 전 단계에서 선택한 것을 현재 단계에서 선택하지 못한다는 점에서 동일한 구조를 가진 문제다.

백링크