バー準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]));
	}

}