21.09.17 기록

백준 알고리즘 1149 풀이

🎆나의 오답

-손코딩을 해보다가 dfs(백트래킹)로 풀면 되지 않을까..? 하고 시도해봤다.
-하지만 문제에서 주어진 조건을 어떻게 풀어내야할지 막막해서 결국 풀지 못했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B1149 {
    public static int N;
    public static int[][] RGB;
    public static int min = Integer.MAX_VALUE;
    public static int sum = 0;
    public static boolean[] check = new boolean[3];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        RGB = new int[N][3];

        StringTokenizer st;
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < N; j++) {
                RGB[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        getMin(0);
        System.out.println(min);
    }

    public static void getMin(int depth) {
        if(depth == N) {
            min = Math.min(sum, min);
            sum = 0;
            return;
        }

        if(depth == 2) {
            check[0] = false;
        }

        for(int i = 0; i < N; i++) {
            if(!check[i]) {
                check[i] = true;
                sum += RGB[depth][i];
                getMin(depth+1);
                check[i] = false;
            }
        }
    }
}

🎆해설

-해설에서는 동적계획법을 사용한 풀이와 반복문을 사용한 풀이 두 가지 방법을 제시한다.
-내용을 이해하는데는 어렵지 않았으나 특히 dp를 사용한 해설은 과연 내가 저렇게 구현할 수 있을까… 하는 마음이 들었다😂

//(1)동적계획법을 사용한 풀이(메모리 14.7MB, 시간 136ms로 통과)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B1149 {
    public final static int RED = 0;
    public final static int GREEN = 1;
    public final static int BLUE = 2;

    public static int[][] cost;
    public 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());
        cost = new int[N][3];
        dp = new int[N][3];

        StringTokenizer st;
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            cost[i][RED] = Integer.parseInt(st.nextToken());
            cost[i][GREEN] = Integer.parseInt(st.nextToken());
            cost[i][BLUE] = Integer.parseInt(st.nextToken());
        }

        dp[0][RED] = cost[0][RED];
        dp[0][GREEN] = cost[0][GREEN];
        dp[0][BLUE] = cost[0][BLUE];

        System.out.println(Math.min(paintCost(N-1, RED), Math.min(paintCost(N-1, GREEN), paintCost(N-1, BLUE))));
    }

    public static int paintCost(int N, int color) {
        if(dp[N][color] == 0) {
            if(color == RED) {
                dp[N][RED] = Math.min(paintCost(N-1, GREEN), paintCost(N-1, BLUE)) + cost[N][RED];
            }
            else if(color == GREEN) {
                dp[N][GREEN] = Math.min(paintCost(N-1, RED), paintCost(N-1, BLUE)) + cost[N][GREEN];
            }if(color == BLUE) {
                dp[N][BLUE] = Math.min(paintCost(N-1, RED), paintCost(N-1, GREEN)) + + cost[N][BLUE];
            }
        }
        return dp[N][color];
    }
}

//(2)반복문을 사용한 풀이(메모리 14.7MB, 시간 132ms로 통과)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//2. 해설(2) - 반복문 사용
public class B1149 {
    public final static int RED = 0;
    public final static int GREEN = 1;
    public final static int BLUE = 2;

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

        int N = Integer.parseInt(br.readLine());

        int[][] cost = new int[N][3];
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            cost[i][RED] = Integer.parseInt(st.nextToken());
            cost[i][GREEN] = Integer.parseInt(st.nextToken());
            cost[i][BLUE] = Integer.parseInt(st.nextToken());
        }

        for(int i = 1; i < N; i++) {
            cost[i][RED] += Math.min(cost[i-1][GREEN], cost[i-1][BLUE]);
            cost[i][GREEN] += Math.min(cost[i-1][RED], cost[i-1][BLUE]);
            cost[i][BLUE] += Math.min(cost[i-1][RED], cost[i-1][GREEN]);
        }

        System.out.println(Math.min(Math.min(cost[N-1][RED], cost[N-1][GREEN]), cost[N-1][BLUE]));
    }
}