[백준] no1149: RGB거리

문제

     * 순서대로 RGB를 칠하는 방법 중 최소비용을 구하기
     * Input : 빨강 초록 파랑 순으로 비용이 주어진다.
     * Output : 총 비용 중 최소합 구하기
     * 단, 양옆으로는 현재 색과 다른 색이어야 한다.

문제 링크 : https://www.acmicpc.net/problem/1149

---

풀이방법

1. 일반 재귀 : 메모리 초과

2. DP를 이용한 방법 (레퍼런스)

---

나의 코드

1. 첫 번째 기준으로 3개의 배열을 만들어 각각의 최소값을 구한 후 최종 값을 비교해서 min값 찾기 [실패]

: 입력마다 들어오는 다음 값 중 중복되지않는 색 중 더 작은 값을 구하는 방식을 사용했기때문에, 

중간에 더 큰값을 더하더라도 결과적으로 제일 작은 값이 나올 수 있는 경우가 배제되버림

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int T = Integer.parseInt(br.readLine());
    StringTokenizer first = new StringTokenizer(br.readLine(), " ");

    int[] arrR = new int[T];
    int[] arrG = new int[T];
    int[] arrB = new int[T];

    arrR[0] = Integer.parseInt(first.nextToken());
    arrG[0] = Integer.parseInt(first.nextToken());
    arrB[0] = Integer.parseInt(first.nextToken());

    String checkR = "R";
    String checkG = "G";
    String checkB = "B";

    for(int i=1; i<T ; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int R = Integer.parseInt(st.nextToken());
        int G = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        // arrR
        if(checkR.equals("R")) {
            if(G<=B) {
                arrR[i] = arrR[i-1] + G;
                checkR = "G";
            }
            else {
                arrR[i] = arrR[i-1] + B;
                checkR = "B";
            }
        } else if(checkR.equals("G")) {
            if(R<=B) {
                arrR[i] = arrR[i-1] + R;
                checkR = "R";
            }
            else {
                arrR[i] = arrR[i-1] + B;
                checkR = "B";
            }
        } else {
            if(R<=G) {
                arrR[i] = arrR[i-1] + R;
                checkR = "R";
            }
            else {
                arrR[i] = arrR[i-1] + G;
                checkR = "G";
            }
        }

        // arrG
        if(checkG.equals("R")) {
            if(G<=B) {
                arrG[i] = arrG[i-1] + G;
                checkG = "G";
            }
            else {
                arrG[i] = arrG[i-1] + B;
                checkG = "B";
            }
        } else if(checkG.equals("G")) {
            if(R<=B) {
                arrG[i] = arrG[i-1] + R;
                checkG = "R";
            }
            else {
                arrG[i] = arrG[i-1] + B;
                checkG = "B";
            }
        } else {
            if(R<=G) {
                arrG[i] = arrG[i-1] + R;
                checkG = "R";
            }
            else {
                arrG[i] = arrG[i-1] + G;
                checkG = "G";
            }
        }

        // arrB
        if(checkB.equals("R")) {
            if(G<=B) {
                arrB[i] = arrB[i-1] + G;
                checkB = "G";
            }
            else {
                arrB[i] = arrB[i-1] + B;
                checkB = "B";
            }
        } else if(checkB.equals("G")) {
            if(R<=B) {
                arrB[i] = arrB[i-1] + R;
                checkB = "R";
            }
            else {
                arrB[i] = arrB[i-1] + B;
                checkB = "B";
            }
        } else {
            if(R<=G) {
                arrB[i] = arrB[i-1] + R;
                checkB = "R";
            }
            else {
                arrB[i] = arrB[i-1] + G;
                checkB = "G";
            }
        }
    }

    List<Integer> results = new ArrayList<>();
    results.add(arrR[arrR.length-1]);
    results.add(arrG[arrG.length-1]);
    results.add(arrB[arrB.length-1]);

    int result = Collections.min(results);
    System.out.println(result);
}

 

2. 재귀를 이용한 방법 : 모든 합을 구한 뒤, 그 중 제일 작은값을 반환 [메모리 초과]

private static List<Integer> results = new ArrayList<>();
private static int T;
private static int[][] map;
private static String[] firstRGB = {"R", "G", "B"};

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    T = Integer.parseInt(br.readLine());
    map = new int[T][3];
    for(int i=0; i<T ; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        map[i][0] = Integer.parseInt(st.nextToken());
        map[i][1] = Integer.parseInt(st.nextToken());
        map[i][2] = Integer.parseInt(st.nextToken());
    }

    for(int i=0; i<3; i++) {
        Check now = new Check(map[0][i], firstRGB[i], 0);
        recur(now);
    }

    int result = Collections.min(results);
    System.out.println(result);
}


private static void recur (Check now) {
    if(now.Order==T-1) results.add(now.Sum);
    else {
        if(now.RGB.equals("R")) {
            recur(new Check(now.Sum + map[now.Order+1][1], "G", now.Order+1));
            recur(new Check(now.Sum + map[now.Order+1][2], "B", now.Order+1));
        }
        else if (now.RGB.equals("G")) {
            recur(new Check(now.Sum + map[now.Order+1][0], "R", now.Order+1));
            recur(new Check(now.Sum + map[now.Order+1][2], "B", now.Order+1));
        }
        else {
            recur(new Check(now.Sum + map[now.Order+1][0], "R", now.Order+1));
            recur(new Check(now.Sum + map[now.Order+1][1], "G", now.Order+1));
        }
    }
}

private static class Check {
    private int Sum;
    private String RGB;
    private int Order;

    public Check (int sum, String rgb, int order) {
        this.Sum = sum;
        this.RGB = rgb;
        this.Order = order;
    }
}

 

---

레퍼런스 코드

DP를 이용한 방법

final static int R = 0;
final static int G = 1;
final static int B = 2;
static int[][] map;
static int[][] DP;

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());
    map = new int[N][3];
    DP = new int[N][3];

    StringTokenizer st;
    for(int i = 0; i < N; i++) {

        st = new StringTokenizer(br.readLine(), " ");

        map[i][R] = Integer.parseInt(st.nextToken());
        map[i][G] = Integer.parseInt(st.nextToken());
        map[i][B] = Integer.parseInt(st.nextToken());
    }

    DP[0][R] = map[0][R];
    DP[0][G] = map[0][G];
    DP[0][B] = map[0][B];


    System.out.println(Math.min(recur(N- 1, R), Math.min(recur(N - 1, G), recur(N - 1, B))));
}

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

        if(color == R) {
            DP[N][R] = Math.min(recur(N - 1, G), recur(N - 1, B)) + map[N][R];
        }
        else if(color == G) {
            DP[N][G] = Math.min(recur(N - 1, R), recur(N - 1, B)) + map[N][G];
        }
        else {
            DP[N][B] = Math.min(recur(N - 1, R), recur(N - 1, G)) + map[N][B];
        }

    }
    return DP[N][color];
}

참고 링크 : https://st-lab.tistory.com/128