boj 1149 RGB [DP]

https://www.acmicpc.net/problem/1149

DP를 이용한 문제.

Home[i][j] = i번째집을 j색상으로 칠하려할때 i번째 집까지 도색할때 드는 최소 비용

RGB[j] = 현재 집을 j색상으로 칠하려 할때 드는 비용

바로 이전 집의 모든 색상에 대해서 최소값을 비교하여 최소 값을 유지하는 방식

코드

import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class boj1149 { static int N; static int[][] Home; static int[] RGB; public static void main(String[] args) throws IOException { System.setIn(new FileInputStream("res/input1149.txt")); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Home = new int[1001][3]; RGB = new int[3]; N = Integer.parseInt(br.readLine()); StringTokenizer token; for (int i = 1; i < N+1; i++) { token = new StringTokenizer(br.readLine(), " "); for (int j = 0; j < 3; j++) { RGB[j] = Integer.parseInt(token.nextToken()); Home[i][j] = Math.min(Home[i-1][(j+1)%3], Home[i-1][(j+2)%3]) + RGB[j]; } } System.out.println(Math.min(Home[N][0], Math.min(Home[N][1], Home[N][2]))); } }