boj 17404 RGB거리 2

www.acmicpc.net/problem/17404

17404번: RGB거리 2

 

www.acmicpc.net/problem/1149

1149번: RGB거리

위의 문제에서 1번 집과 N번 집도 이웃이라는 조건이 추가되었습니다.

 

저는 1번 집에 칠할 색을 고정시켜놓고 모든 집을 칠하는 비용의 최솟값을 구하였습니다.

색이 3가지이므로 최솟값은 3번 구하게 되며, 1번 집이 빨강일 경우, 초록일 경우, 파랑일 경우를 따로 구해줍니다.

solve함수는 위의 문제와 동일하게 돌아갑니다.

 

1번 집이 빨강일 경우에는 N번 집이 초록, 파랑을 골랐을 때의 최솟값

1번 집이 초록일 경우에는 N번 집이 빨강, 파랑을 골랐을 때의 최솟값

1번 집이 파랑일 경우에는 N번 집이 빨강, 초록을 골랐을 때의 최솟값

으로 갱신해줍니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][], dp[][];
    static int N, ans;
 
    static void solve() {
        for (int i = 2; i <= N; i++) {
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + list[i][0];
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + list[i][1];
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + list[i][2];
        }
    }
 
    static void func() {
        dp[1][0] = list[1][0];
        dp[1][1] = 1001;
        dp[1][2] = 1001;
        solve();
        ans = Math.min(dp[N][1], dp[N][2]);
 
        dp[1][0] = 1001;
        dp[1][1] = list[1][1];
        dp[1][2] = 1001;
        solve();
        ans = Math.min(ans, Math.min(dp[N][0], dp[N][2]));
 
        dp[1][0] = 1001;
        dp[1][1] = 1001;
        dp[1][2] = list[1][2];
        solve();
        ans = Math.min(ans, Math.min(dp[N][0], dp[N][1]));
        
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N + 1][3];
        dp = new int[N + 1][3];
 
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = Integer.parseInt(st.nextToken());
            list[i][2] = Integer.parseInt(st.nextToken());
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}