[백준] RGB거리

🔗 문제 보기 - [백준] RGB거리

📖 문제

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

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

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

✍ 입력

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

📄 출력

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

✅ 코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.Arrays;  
import java.util.StringTokenizer;  
  
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());  
        int[][] arr = new int[n][3];  
  
        StringTokenizer st;  
        for(int i=0; i<n; i++) {  
            st = new StringTokenizer(br.readLine());  
            int r = Integer.parseInt(st.nextToken());  
            int g = Integer.parseInt(st.nextToken());  
            int b = Integer.parseInt(st.nextToken());  
            arr[i][0] = r;  
            arr[i][1] = g;  
            arr[i][2] = b;  
        }
        
        for(int i=1; i<n; i++) {  
            arr[i][0] += Math.min(arr[i-1][1], arr[i-1][2]);  
            arr[i][1] += Math.min(arr[i-1][0], arr[i-1][2]);  
            arr[i][2] += Math.min(arr[i-1][0], arr[i-1][1]);  
        }  
        System.out.println(Arrays.stream(arr[n-1]).min().getAsInt());  
    }  
}

🧩 코드풀이

문제를 이해하는데 시간이 좀 소요됐지만 이해하면 간단하게 DP 알고리즘으로 풀 수 있는 문제였습니다.

반복문을 돌면서 입력 받은 값들을 arr 배열에 입력 후 각각 조건에 맞게 값을 더해주면 되는데, 각각 선택한 index를 제외한 나머지 두개의 값을 비교하여 그 값을 더해줍니다.

이유는 문제 조건 중 아래와 같은 내용들이 있기 때문 입니다.

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

이렇게 반복문을 마치고, 마지막 배열 인덱스에서 가장 작은 값을 stream을 이용하여 구해주고 출력해줍니다.