DP - 1149. RGB거리

문제

www.acmicpc.net/problem/1149

1149번: RGB거리

 

잠깐만

최소 비용을 어떻게 계산해야 할까요?

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int houseNum = Integer.parseInt(st.nextToken()); 
		int redHouse = 0, greenHouse = 0, blueHouse = 0; 
		
		for (int i = 1; i <= houseNum; i++) {
			st = new StringTokenizer(br.readLine());
			
			int red = Integer.parseInt(st.nextToken()) + Math.min(greenHouse, blueHouse);
			int green = Integer.parseInt(st.nextToken()) + Math.min(redHouse, blueHouse);
			int blue = Integer.parseInt(st.nextToken()) + Math.min(redHouse, greenHouse);
			
			redHouse = red;
			greenHouse = green;
			blueHouse = blue;
		}
		
		System.out.print(Math.min(redHouse, Math.min(greenHouse, blueHouse)));
	}
}

 

설명

red를 칠하기 위해선, 이전 green, blue 집의 최소비용을 가져와야 하구요

green을 칠하기 위해선, 이전 red, blue 집의 최소비용을 가져와야 해요

blue를 칠하기 위해선 이전 red, green집의 최소비용 값을 가져와야해요

이렇게 순차적으로 계산해 나아가면 됩니다.

최종 비용은, 최소 값을 출력해주면 되겠죠?

 

회고

처음엔, [i][3]의 배열을 선언하여 구현했어요. 생각해보니, 이전 집 비용 외 사용하지 않다는걸 깨닫고,

이중배열을 사용할 필욘 없겠더라구요.

필요 없는 메모리 낭비는 없으면 좋잖아요?

 

하지만 아래의 코드가 훨씬 더 이해하기 쉬워 보입니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int houseNum = Integer.parseInt(st.nextToken()); 
		int[][] houseMoney = new int[houseNum+1][3];
		
		for (int i = 1; i <= houseNum; i++) {
			st = new StringTokenizer(br.readLine());
			int red = Integer.parseInt(st.nextToken());
			int green = Integer.parseInt(st.nextToken());
			int blue = Integer.parseInt(st.nextToken());
			
			houseMoney[i][0] = red + Math.min(houseMoney[i-1][1], houseMoney[i-1][2]);
			houseMoney[i][1] = green + Math.min(houseMoney[i-1][0], houseMoney[i-1][2]);
			houseMoney[i][2] = blue + Math.min(houseMoney[i-1][0], houseMoney[i-1][1]);
		}
		
		System.out.print(Math.min(houseMoney[houseNum][0], Math.min(houseMoney[houseNum][1], houseMoney[houseNum][2])));
	}
}