[백준] RGB거리 (1149번 JAVA) (!) / 401 - 다이나믹 프로그래밍 1 (연습)

[백준] RGB거리 (1149번 JAVA) (!) / 401 - 다이나믹 프로그래밍 1 (연습)

---

[접근 방법]

첫 번째 집을 칠하는 경우에 따라 모든 경우를 전수조사 해야한다.

전수조사 를 해야 한다는 것이 가장 중요!

 

1. 첫 번째 집을 빨간색 으로 칠하는 경우

2. 첫 번째 집을 초록색 으로 칠하는 경우

3. 첫 번째 집을 파란색 으로 칠하는 경우

 

1, 2, 3 방법 중 최솟값을 선택

---

[JAVA 코드]

1. N번째 집부터 1번째 집까지 Top-Down 방식

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main{

    // Red = 0 , Green = 1, Blue = 2
    final static int Red = 0;
    final static int Green = 1;
    final static int Blue = 2;

    public static int[][] DP;
    public static int[][] arr;

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // (2 ≤ N ≤ 1,000)
        int N = Integer.parseInt(br.readLine());
        arr = new int[N][3];

        // input data
        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][Red] = Integer.parseInt(st.nextToken());
            arr[i][Green] = Integer.parseInt(st.nextToken());
            arr[i][Blue] = Integer.parseInt(st.nextToken());
        }
        
        /*
        DP[N-1][Red] = 첫 집을 빨간색으로 칠했을 경우 N번째 까지의 합의 최솟값
        */

        // 초기값 설정
        DP = new int[N][3];
        DP[0][Red] = arr[0][Red];
        DP[0][Green] = arr[0][Green];
        DP[0][Blue] = arr[0][Blue];
        
        // N번째 집을 R, G, B로 칠하기 시작하는 각각의 경우 중 최솟값
        bw.write( Math.min(Math.min(recur(N-1, Red), recur(N-1, Green)), recur(N-1, Blue)) + "\n");

        bw.flush();
        bw.close();
    }

    public static int recur(int N, int color) {
        if (DP[N][color] == 0){

            if(color == Red) {
                DP[N][Red] = Math.min(recur(N - 1, Green), recur(N - 1, Blue)) + arr[N][Red];
            }
            else if(color == Green) {
                DP[N][Green] = Math.min(recur(N - 1, Red), recur(N - 1, Blue)) + arr[N][Green];
            }
            else{
                DP[N][Blue] = Math.min(recur(N - 1, Red), recur(N - 1, Green)) + arr[N][Blue];
            }
        }

        return DP[N][color];
    }
}

 

2. 1번째 집부터 N번째 집까지 Botton-Up 방식

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main{

    // Red = 0 , Green = 1, Blue = 2
    final static int Red = 0;
    final static int Green = 1;
    final static int Blue = 2;

    public static int[][] arr;

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // (2 ≤ N ≤ 1,000)
        int N = Integer.parseInt(br.readLine());
        arr = new int[N][3];

        // input data
        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][Red] = Integer.parseInt(st.nextToken());
            arr[i][Green] = Integer.parseInt(st.nextToken());
            arr[i][Blue] = Integer.parseInt(st.nextToken());
        }
        
        for(int i=1; i<N; i++){
            arr[i][Red] += Math.min(arr[i-1][Green], arr[i-1][Blue]);
            arr[i][Green] += Math.min(arr[i-1][Red], arr[i-1][Blue]);
            arr[i][Blue] += Math.min(arr[i-1][Red], arr[i-1][Green]);
        }

        int result = Math.min(arr[N-1][Red], arr[N-1][Green]);
        result =  Math.min(result, arr[N-1][Blue]);

        bw.write(result + "\n");
        bw.flush();
        bw.close();
    }
}

+) Math.min () 함수는 인자를 2개만 받을 수 있다.

 

https://docs.oracle.com/javase/7/docs/api/

Java Platform SE 7