문제

나의 풀이

public class Pracc {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ArrayList<int[]> s = new ArrayList<>();     // 각 행을 리스트로 묶어 저장
        int[] color = new int[N];                   // 각 행별 최소값 저장
        int[] sum = new int[3];                     // 최소값을 더한 값을 저장

        while (N > 0) {                                                 // 리스트 형식으로 저장
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int[] list = new int[] {a, b, c};
            s.add(list);

            N--;
        }

        for (int i = 0; i < 3; i++) {
            int min = s.get(0)[i];			// 첫 행 리스트에서 index 0번째 값
            color[0] = min;
            int total = 0;

            for (int j = 1; j < s.size(); j++) {
                int last = color[j - 1];
                int min2 = 0;
                if (last == s.get(j-1)[0]) {	 // index 0번째 값이었다면 index 1, 2 중 작은 값
                    min2 = Math.min(s.get(j)[1], s.get(j)[2]);
                } else if (last == s.get(j-1)[1]) {
                    min2 = Math.min(s.get(j)[0], s.get(j)[2]);
                } else {
                    min2 = Math.min(s.get(j)[0], s.get(j)[1]);
                }
                color[j] = min2;
            }

            for (int k = 0; k < s.size(); k++) {
                total += color[k];			// 작은 값을 넣어놓은 리스트의 합
            }

            sum[i] = total;				    // 합을 sum리스트에 넣음
        }

        int answer = Math.min(Math.min(sum[0], sum[1]), Math.min(sum[1], sum[2]));
		// sum리스트 값 중 가장 작은 값을 출력


        System.out.println(answer);


    }
}

• 반드시 작은 값들로만 채웠을 때 최종적으로 최소값이 나오지 않기 때문에
  정확한 값 산출 x
• 앞 행, 다음 행 들의 합을 모두 고려하여 최소값이 나오도록 함수 생성해야 함

반복문 풀이

public class Pracc {
    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][0] = Integer.parseInt(st.nextToken());
            Cost[i][1] = Integer.parseInt(st.nextToken());
            Cost[i][2] = Integer.parseInt(st.nextToken());

        }

        // 1부터 N-1까지 각 i별 i-1의 서로 다른 색상 중 최솟값을 누적하여 더한다.
        for (int i = 1; i < N; i++) {                           // 다음 행의 값에 이전 행의 다른 index를 가진 값 중 최소값을 더한다
            Cost[i][0] += Math.min(Cost[i - 1][1], Cost[i - 1][2]);
            Cost[i][1] += Math.min(Cost[i - 1][0], Cost[i - 1][2]);
            Cost[i][2] += Math.min(Cost[i - 1][0], Cost[i - 1][1]);
        }

        System.out.println(Math.min(Math.min(Cost[N - 1][0], Cost[N - 1][1]), Cost[N - 1][2]));
    }
}

재귀 풀이

public class Pracc {
    static int[][] Cost;
    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][0] = Integer.parseInt(st.nextToken());
            Cost[i][1] = Integer.parseInt(st.nextToken());
            Cost[i][2] = Integer.parseInt(st.nextToken());
        }

        // DP의 첫번째 값(집)은 각 색상비용의 첫번째 값으로 초기화
        DP[0][0] = Cost[0][0];
        DP[0][1] = Cost[0][1];
        DP[0][2] = Cost[0][2];


        System.out.println(Math.min(cost(N- 1, 0), Math.min(cost(N - 1, 1), cost(N - 1, 2))));
    }

    static int cost(int N, int n) {

        // 만약 탐색하지 않은 배열이라면
        if(DP[N][n] == 0) {

            // color의 색에 따라 이전 집의 서로 다른 색을 재귀호출하여 최솟값과 현재 집의 비용을 더해서 DP에 저장한다
            if(n == 0) {
                DP[N][0] = Math.min(cost(N - 1, 1), cost(N - 1, 2)) + Cost[N][0];
            }
            else if(n == 1) {
                DP[N][1] = Math.min(cost(N - 1, 0), cost(N - 1, 2)) + Cost[N][1];
            }
            else {
                DP[N][2] = Math.min(cost(N - 1, 0), cost(N - 1, 1)) + Cost[N][2];
            }

        }

        return DP[N][n];
    }
}

• for문 돌리는 방식을 재귀로 구현

1194번 재귀 풀이