백준 1149 RGB거리

백준 1149 RGB거리

백준 1149 RGB거리

구현 전 생각

이전의 색을 비교하여 같은 경우 이전의 값을 바꾼것과 현재 값을 비교 -> 더 작은것을 선택하는 방식

---

아쉬운점

구현 전 생각으로 코드를 작성하게 되면 지역최소값을 찾을 수 있지만 전체적으로 봤을때는 최소값이 아닐 가능성이 매우 높다 -> 따라서 DP로 해결한다. 아직 DP라는 감을 제대로 못잡은거 같다. 확실히 효과적인 알고리즘인만큼 조금 더 공부하자

코드

package com.study37;

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

public class backjoon_1149_RGB거리 {
	static int N;
	static int[][] color;
	public static void main(String[] args) throws NumberFormatException, IOException {
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		color = new int[N][3]; //N번째 집을 (빨강, 초록, 파랑으로 ) 칠하는 비용
		int[][] D = new int[N][3]; //N번째 집을 (빨강, 초록, 파랑으로 ) 칠하는 비용의 최소값 모든 집을 칠하는 비용의 최소값
		StringTokenizer st = null;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 3; j++) {
				color[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		//초기값 -> 첫번째 집을 칠할떄의 비용(집이 한채 밖에 없다를 가정)
		D[0][0]=color[0][0];
		D[0][1]=color[0][1];
		D[0][2]=color[0][2];
		

		//N번재 집의 칠 비용은 n-1번째 집의 가능한 칠 비용 중 더 작은 값으로 선택하면 최소 비용 나올 수 있음
		for (int i = 1; i < N; i++) {
			D[i][0]=Math.min(D[i-1][1],D[i-1][2]) + color[i][0];
			D[i][1]=Math.min(D[i-1][0],D[i-1][2]) + color[i][1];
			D[i][2]=Math.min(D[i-1][0],D[i-1][1]) + color[i][2];
		}
		//n번째 집 까지 칠했을 때의 최소 비용
		System.out.println(Math.min(Math.min(D[N-1][0],D[N-1][1]),D[N-1][2]));
	}

}