[백준/1149] RGB거리 (실버 1) JAVA

package task.easy.rgbstreet1149;

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        
        Deque<int[]> dequeHouse = new ArrayDeque<>();
        
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int red = Integer.parseInt(st.nextToken());   
            int green = Integer.parseInt(st.nextToken());   
            int blue = Integer.parseInt(st.nextToken());
            
            dequeHouse.offer(new int[] {red, green, blue});
        }
        List<Integer> dp = new ArrayList<>();
        int[] colorExpHouseArray = dequeHouse.poll();
        for (int i = 0; i < 3; i++) {
            dp.add(colorExpHouseArray[i]);
        }

        while (!dequeHouse.isEmpty()) {
            int[] poll = dequeHouse.poll();
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < 3; i++) {
                tmp.add(poll[i]);
            }
            int red = Math.min(dp.get(1), dp.get(2)) + tmp.get(0);
            int green = Math.min(dp.get(0), dp.get(2)) + tmp.get(1);
            int blue = Math.min(dp.get(0), dp.get(1)) + tmp.get(2);
            // dp에 업데이트
            dp.set(0, red);
            dp.set(1, green);
            dp.set(2, blue);
        }

        System.out.println(Collections.min(dp));
    }
}

• 최적해 찾기 문제 -> DP일 확률 높음
• 제한시간 짧고, 예시를 그려보면 최대 연산이 3x2^1000이 나옴. 모든 경우의 수 돌면 미친 짓이라는 것을 바로 알 수 있음.
• 점화식을 찾기 위해 N=1~3정도까지는 그려볼만함 -> 아이디어 얻기용
• 결국 목표한 N에서 그 직전을 생각해보면, 그 직전의 집 색깔의 경우의 수는 3개임. 그러므로 N일때의 집은 N-1(3) -> N(6)이 된다. 이걸 그려보면 바로 지워질 부분이 나타남.
• 만약 N에서 red라면 N-1은 green 혹은 blue중의 더 작은 값이어야 함. 그럼 N의 입장에서 N-1을 선택할 수 있음.

N의 red = N-1의 Min(green, blue) + N의 red
N의 green = N-1의 Min(red, blue) + N의 green
N의 blue = N-1의 Min(red, green) + N의 blue

중복 제거 성공. dp는 어떻게든 N과 N-1을 조사해서 중복을 제거할 궁리만 빡세게 하면 여럽지 않은 dp문제는 빠르게 아이디어를 얻을 수 있다.

즉 6개가 3개가 되므로 모든 경우의수를 조사했을 때 연산수인 32의1000승이 아니라 31000으로 바뀜.

원리만 알면 코드는 1분 컷. dp 아이디어 찾기 자체는 쉬웠다. dp문제는 복잡한 코딩인 문제가 없으므로 아이디어만 확정되면 코딩은 1분컷 가능.