[BAEKJOON] 1149 RGB거리

문제 요약

• 알고리즘 분류: 동적계획법
• 난이도: Silver1
• 문제내용:
  • 빨강, 초록, 파랑색의 N개 집이 있다. 그리고 각 집에 각 색에 칠하는 색의 비용이 있다.
  • i번째와와 i-1, i + 1번째 색은 달라야 한다.
  • 모든 집의 최소 비용으로  칠하는 비용을 구하여라
• 사이트 주소: https://www.acmicpc.net/problem/1149

1149번: RGB거리

 

문제풀이

문제 접근 방법

 이 문제는 동적계획법이다. 그래서 점화식을 짜는 방법만 알면 된다.

  위 그림은 예제 1번을 그림으로 표현한것이다. 2번째 집 부터 보면 레드는 1번째 블루와 그린 중 가장 작은 값이랑 더하고 저장 하면 된다.  블루는 1번째 레드와 그린중 가장 작은 값이랑 더하면된다. 그린은 1번째 레드와 블루중 가장 적은 값을 더해서 저장 하면된다. 3번째 도 이전 방식처럼 계속해서 모든 집 최소 가치 값을 더하면된다.

1. 2번째 인덱스 부터 for문을 돌리면 된다.
2. i 번째  레드는 i -1 번째 블루, 그린 중 작은 값을 더하면된다. 블루는 i - 1번째 레드, 그린 중 작은 값을 더하면된다. i -1 번째 그린은 레드, 블루 중 작은 값을 더하면된다.
3. 최종 출력은 마지막 인덱스중 가장 작은 값이다.  

CODE

Python

import sys

input = sys.stdin.readline

size = int(input())

houses = [list(map(int, input().split())) for _ in range(size)]

for i in range(1, size):
    houses[i][0] += min(houses[i-1][1], houses[i-1][2])
    houses[i][1] += min(houses[i-1][0], houses[i-1][2])
    houses[i][2] += min(houses[i-1][0], houses[i-1][1])
    
print(min(houses[-1]))

Java

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));
		StringTokenizer st;
		int size = Integer.parseInt(br.readLine());
		
		int[][] house = new int[size][3];
		
		
		for(int i =0; i < size; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 3; j++) {
				house[i][j] = Integer.parseInt(st.nextToken());
			}			
		}
		
		for(int i = 1; i < size; i++) {
			house[i][0] += Math.min(house[i-1][1], house[i-1][2]);
			house[i][1] += Math.min(house[i-1][0], house[i-1][2]);
			house[i][2] += Math.min(house[i-1][1], house[i-1][0]);
		}
		
		System.out.println(Arrays.stream(house[size-1]).min().getAsInt());
	}
	
}