[BOJ 1149] RGB거리 (Java, DP)

 

---

문제 링크

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

1149번: RGB거리

---

문제 풀이 

- 시간 제한 0.5초 이므로 완전 탐색으로 풀 경우 시간 초과 발생 

- 첫번째 집의 RGB 값으로 초기값을 설정하고, 동적 프로그래밍으로 풀이한다

- 최종적으로 DP[N][1 ~ 3] 값 중 최소값 출력

- 시간복잡도 : O(N)

 

점화식
DP[i][j] = Math.min(DP[i - 1][x], DP[i - 1][y]) + RGB[i][j] (이때 i != x != y )

DP[N][1] = Math.min(DP[N - 1][2], DP[N - 1][3]) + RGB[N][1];
DP[N][2] = Math.min(DP[N - 1][1], DP[N - 1][3]) + RGB[N][2];
DP[N][3] = Math.min(DP[N - 1][1], DP[N - 1][2]) + RGB[N][3];

 

---

제출 코드

(1) Bottom-Up 방식

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();
    static InputProcessor inputProcessor = new InputProcessor();

    static int[][] DATA, DP;
    static int N;

    public static void main(String[] args) throws IOException {
        input();
        pro();
        output();
    }

    private static void input() {
        N = inputProcessor.nextInt();
        DATA = new int[N + 1][4];
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= 3; j++) {
                DATA[i][j] = inputProcessor.nextInt();
            }
        }
		
        // 초기화
        DP = new int[N + 1][4];
        for(int i = 1; i <= 3; i++) {
            DP[1][i] = DATA[1][i];
        }
    }

    private static void pro() {
        bottomUp();
    }

    private static void bottomUp() {
        for(int i = 2; i <= N; i++) {
            DP[i][1] = Math.min(DP[i - 1][2], DP[i - 1][3]) + DATA[i][1];
            DP[i][2] = Math.min(DP[i - 1][1], DP[i - 1][3]) + DATA[i][2];
            DP[i][3] = Math.min(DP[i - 1][1], DP[i - 1][2]) + DATA[i][3];
        }

        int result = Math.min(DP[N][1], Math.min(DP[N][2], DP[N][3]));
        sb.append(result);
    }


    private static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static class InputProcessor {
        BufferedReader br;
        StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String input = "";
            try {
                input = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return input;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
    
}

 

 

(2) Top-Down 방식

- 재귀 함수에서 종료 및 반환 조건 처리 하지 않을 경우 시간 초과 발생

- 이미 구해진 값이 있는 경우 반환해주기 (메모리제이션*)

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();
    static InputProcessor inputProcessor = new InputProcessor();

    static int[][] DATA, DP;
    static int N;

    public static void main(String[] args) throws IOException {
        input();
        pro();
        output();
    }

    private static void input() {
        N = inputProcessor.nextInt();
        DATA = new int[N + 1][4];
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= 3; j++) {
                DATA[i][j] = inputProcessor.nextInt();
            }
        }
        
        // 초기화
        DP = new int[N + 1][4];
        for(int i = 1; i <= 3; i++) {
            DP[1][i] = DATA[1][i];
        }
    }

    private static void pro() {
        int result = Math.min(topDown(N, 1), Math.min(topDown(N , 2), topDown(N , 3)));
        sb.append(result);
    }


    private static int topDown(int row, int col) {
        if(row < 1) return 0;
        if(DP[row][col] != 0) return DP[row][col];

        if(col == 1) {
            DP[row][col] = Math.min(topDown(row - 1, 2), topDown(row - 1, 3)) + DATA[row][col];
        } else if(col == 2) {
            DP[row][col] = Math.min(topDown(row - 1, 1), topDown(row - 1, 3)) + DATA[row][col];
        } else if(col == 3) {
            DP[row][col] = Math.min(topDown(row - 1, 1), topDown(row - 1, 2)) + DATA[row][col];
        }

        return DP[row][col];
    }

    private static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static class InputProcessor {
        BufferedReader br;
        StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String input = "";
            try {
                input = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return input;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
    
}