Baekjoon Online Judge _ 01149 _ RGB 거리

[ Baekjoon Online Judge _ 01149 _ RGB 거리 ]

문제

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다.

출력

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

예제 입력

3
26 40 83
49 60 57
13 89 99

예제 출력

96

풀이

처음에 접근한 방법은 입력들을 받아 배열에 저장한 뒤

세 가지 경우로 나눈다.

첫번째는 맨처음집에 R을 선택한 경우, 두번째는 맨처음집에 G를 선택한 경우, 세번째는 맨처음집에 B를 선택한 경우.

각 경우마다 다음집으로 옮겨가며 그 전에 선택했던 색이 아닌 두 색의 비용을 비교해서 선택한다.

이 경우 그 전에 어떤 색을 선택했는지 저장해두는 변수가 필요하다.

그리고 마지막에 세 가지 경우를 비교해 가장 비용이 적은 것을 답으로 택한다.

이 방법은 그냥 단순하게 푼 방법이였고 더 좋은 방법이 있을 것 같앗다!

그래서 찾아보다가 훨씬 간단한 방법을 찾았다.

이건 처음에 두번째 집부터 시작해서

그 전 집의 색을 선택한다. (현재 집의 색이 아닌 두가지 색중 작은 것을 고른다)

예를 들어 현재 집에 R을 선택할 것이라면, 이전 집에서 G와 B중 작은 것을 선택해 현재 집의 R 값과 더하고 저장.

이런식으로 계속 누적해서 더해간다.

그럼 배열의 마지막엔 세 가지 경우에 대해 총 합이 저장되게된다.

바로 이해하긴 힘들지만 잘 생각해보면 이해할 수 있다!!

이런 방법을 스스로 생각해 낼 수 있게 더 공부해야겠다 ^^!

코드

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args){
        int red, green, blue, min;
        
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); //집의개수(1~1000)
    
        int[][] cost = new int[3][N];
        
        cost[0][0] = sc.nextInt();
        cost[1][0]= sc.nextInt();
        cost[2][0] = sc.nextInt();
        
        for(int i = 1; i < N; i++){
            red = sc.nextInt();
            green = sc.nextInt();
            blue = sc.nextInt();        
            cost[0][i] = red + Math.min(cost[1][i-1], cost[2][i-1]);
            cost[1][i] = green + Math.min(cost[0][i-1], cost[2][i-1]);
            cost[2][i] = blue + Math.min(cost[0][i-1], cost[1][i-1]);
        }
        
        min = Math.min(Math.min(cost[0][N-1], cost[1][N-1]), cost[2][N-1]);
        System.out.println(min);
        
    }
}