백준 1149번-RGB거리(JAVA)

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

1149번: 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.StringTokenizer;

public class BJ_01149 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		//입력부
		int N = Integer.parseInt(br.readLine());
		int[][] color_cost = new int[N][3];
		for (int n = 0; n < N; n++) {
			String str = br.readLine();
			st = new StringTokenizer(str, " ");
			for(int f = 0; f <3; f++) {
				color_cost[n][f] =Integer.parseInt(st.nextToken());
			}
		}
		//i를 선택하는 가장 작은 min찾기
		//메모 배열
		int[][] memo = new int[N][3];
	
		//집이 1개일 때 초기화
		for(int i = 0; i < 3; i++) {
			memo[0][i] = color_cost[0][i];
		}
		
		//집이 2개 이상일 때
		int D_min = Integer.MAX_VALUE;
		for(int i = 1; i < N; i++) {
			for(int j = 0; j <3; j++) {
				D_min = Integer.MAX_VALUE;
				for(int k = 0; k < 3; k++) {
					if(j != k && D_min >= memo[i-1][k]+color_cost[i][j]) {
						D_min = memo[i-1][k]+color_cost[i][j];
						memo[i][j] = D_min;
					}
				}
			}
		}
		
		//마지막 memo 배열에서 최솟값 찾기
		int result = Integer.MAX_VALUE;
		for(int i = 0; i < 3; i++) {
			if(memo[N-1][i] <result) {
				result = memo[N-1][i];
			}
		}
		
		System.out.println(result);
	
	}
}

 

n번째 집이 n-1번 집과 다른 색을 선택하는 경우의 최소 비용합을 memo 배열에 저장해 풀이해 주었습니다.