[백준 1149번] RGB거리 - JAVA

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

1149번: RGB거리

풀이

사용한 알고리즘 : DP

 

풀이전략

문제에서 인접한 집들 간에 동일한 색이 칠해지지 않으면 된다고 했다.

즉, 첫번째 집이 빨간색으로 칠해졌다면 두번째 집은 빨간색이 아닌 초록색이라 파란색으로 칠해져야한다.

그리고 세번째집은 두번째 집이 칠해지지 않은 두 가지 색중 하나로 칠해져야한다.

 

int d[][] = new int[N][3] 라는 2차원 배열은 특정 인덱스에서 각각의 색을 칠했을 경우 최소값을 나타낸다.

 

d[i][0]은 i번째 인덱스에서 빨간색을 칠했을 경우,

d[i][1]은 i번째 인덱스에서 초록색을 칠했을 경우,

d[i][2]는 i번째 인덱스에서 파란색을 칠했을 경우를 뜻한다.

 

지금까지 설명한 내용을 위 배열을 사용해 수학적으로 나타내면

d[i][0]=Math.min(d[i-1][1],d[i-1][2])+red; 

d[i][1]=Math.min(d[i-1][0],d[i-1][2])+green;
d[i][2]=Math.min(d[i-1][0],d[i-1][1])+blue;

로 나타낼 수 있다.

(red, green, blue는 i번째 인덱스에서의 특정 색상을 칠했을 경우의 값을 뜻한다.)

 

우리가 최종적으로 구하고자하는 결과는 N번째 집까지 칠했을 경우의 최솟값이므로

d[N][0], d[N][1], d[N][2] 중 가장 작은 값을 출력하면 된다.

 

제출코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int d[][]=new int[N+1][3];

        for(int i=1;i<N+1;++i){
            st=new StringTokenizer(br.readLine());
            int red=Integer.parseInt(st.nextToken());
            int green=Integer.parseInt(st.nextToken());
            int blue=Integer.parseInt(st.nextToken());

            d[i][0]=Math.min(d[i-1][1],d[i-1][2])+red;
            d[i][1]=Math.min(d[i-1][0],d[i-1][2])+green;
            d[i][2]=Math.min(d[i-1][0],d[i-1][1])+blue;
        }
        int minVal=Math.min(d[N][0],d[N][1]);
        bw.write(Math.min(minVal,d[N][2])+"\n");
        bw.flush();
        bw.close();
    }
}