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

문제

풀이

조건을 어렵게 써놨는데 수학에서 귀납적 증명법에서 따온 것 같았다. 그냥 이웃한 집의 색깔이 같으면 안된다는 조건이다.

처음 봤을 때 프로그래머스의 정수삼각형이 생각났다.

주어진 모양만 삼각형이고 사각형이고 차이지 별다른 차이가 없었다.

점화식을 세우면

dp[i][0] += Math.min(dp[i - 1][1], dp[i - 1][2]);
dp[i][1] += Math.min(dp[i - 1][0], dp[i - 1][2]);
dp[i][2] += Math.min(dp[i - 1][1], dp[i - 1][0]);

중요한 점은 모든 dp 배열을 채우고 마지막 배열에서 최소값을 구해야 한다는 것이다. (0번째 배열에서 최소값을 시작점으로 잡으면 안되고 모든 점에 대해 다 구해야 함)

코드

dp[i][0] += Math.min(dp[i - 1][1], dp[i - 1][2]);
dp[i][1] += Math.min(dp[i - 1][0], dp[i - 1][2]);
dp[i][2] += Math.min(dp[i - 1][1], dp[i - 1][0]);

dp[i][0]만 보면 0(Red)은 이전 index의 1(Green), 2(Blue) 중 최소값과 더한다
이것을 Green, Blue도 N-1까지 반복하며 dp배열을 채운다.

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

dp배열의 마지막 인덱스(N-1) 중에서 최소값을 찾으면 최소로 더한 정답이 된다.

전체코드

package baekjoon._1149;

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

public class Main {

    static int N;
    static int[][] dp;

    public static void input() {
        FastReader fr = new FastReader();
        N = fr.nextInt();
        dp = new int[N][3];
        for (int i = 0; i < N; i++) {
            dp[i][0] = fr.nextInt();
            dp[i][1] = fr.nextInt();
            dp[i][2] = fr.nextInt();
        }
    }

    public static void main(String[] args) {
        input();
        for (int i = 1; i < N; i++) {
            dp[i][0] += Math.min(dp[i - 1][1], dp[i - 1][2]);
            dp[i][1] += Math.min(dp[i - 1][0], dp[i - 1][2]);
            dp[i][2] += Math.min(dp[i - 1][1], dp[i - 1][0]);
        }

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

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

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

        String next(){
            while(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

        Double nextDouble() { return Double.parseDouble(next()); }

        String nextLine(){
            String str = "";
            try{
                str = br.readLine();
            } catch(IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }

}

느낀점

이번 문제는 그렇게 어렵지 않았지만 문제를 보고 점화식을 구해야겠다고 딱 떠오르진 않았따.
dp문제에 많이 약하다는 느낌을 받아서 시간날 때 다이나믹 프로그래밍 문제들을 많이 풀어 익혀야겠다는 생각이 들었다.