https://www.acmicpc.net/problem/1149
N개의 칸에 색을 칠할건데 이웃한 칸에 같은 색이 칠해지면 안된다
색은 세종류가 있고, 칸마다 그리고 색마다 색칠 비용이 다르다.
이때 모든 칸을 색칠하는 비용의 최소값을 구하시오.
N개의 칸에 색 3개를 재료로 중복순열로 만들고 비용 다 계산해서 최소값을 찾자!
시간복잡도 = O(NX3^N) => O(1000X3^1000)
불가능.
아 어렵네.
어려우면 DP지.
DP를 의심해보자...
문제의 조건을 다시 보도록 하자.
"i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다."
뭔가 수열같은 느낌... 뭔가 점화식이랑 연관있어보이는 느낌...
점화식을 어떻게 만들지?
일반적으론 아래 같은 느낌으로 만드는데...
그리고 다음 순서에서는 앞에서 쓴 색을 제외한 나머지 두색중에서 최소값인 색을 쓰자!
근데 R - B 대신에 B - R 일때 전체비용이 내려갈수도 있는거잖아...
다시 돌아가서 분기를 나눠? 그럼 어디서부터 다시 시작해야되는데??
이건 DP가 아니고 보장받지 못하는 그리디와 가까운것 같다...
확장할 수 있는 방법을 하나 더 생각할 수 있다.
내 뒤에 있는 애가 나만 아니면 된다!
i번째 칸에 R색을 고른다고 할때 i-1번째 칸의 색은 무조건 R색이 아니어야 한다.
이렇게 아주 단순하게 논리를 가져가면 막힘없이 확장할수 있다.
그럼 i번째 칸에는 무조건 R색을 고른다고 가정하고 최소값 비용을 계산하면 어떨까?
그러기 위해서는 i-1번째 칸에는 G,B색이 골랐을때의 전체비용의 최소값이 필요하다.
따라서 점화식은 아래와 같다.
Ri: i번째 칸에 R색을 골랐을때 전체 비용의 최소값
Gi: i번째 칸에 G색을 골랐을때 전체 비용의 최소값
Bi: i번째 칸에 B색을 골랐을때 전체 비용의 최소값
Air: i번째 칸에 R색을 칠하는 비용
Aig: i번째 칸에 G색을 칠하는 비용
Aib: i번째 칸에 B색을 칠하는 비용
Ri = min(Gi-1,Bi-1) + Air
Gi = min(Ri-1,Bi-1) + Aig
Bi = min(Gi-1,Ri-1) + Aib
Ti = min(Ri,Gi,Bi)
import java.io.*;
import java.util.*;
public class BOJ_1149_RGB거리2 {
// 입력루틴
static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tokens;
static StringBuilder output = new StringBuilder();
// 세팅
// 메소드
public static void main(String[] args) throws NumberFormatException, IOException {
// 입력
int N = Integer.parseInt(input.readLine());
int[][] dp = new int[3][N];
tokens = new StringTokenizer(input.readLine());
dp[0][0] = Integer.parseInt(tokens.nextToken());
dp[1][0] = Integer.parseInt(tokens.nextToken());
dp[2][0] = Integer.parseInt(tokens.nextToken());
for (int i = 0+1; i < N; i++) { // 위에서 한번 초항을 설정했으니까 i=0+1
tokens = new StringTokenizer(input.readLine());
int Air = Integer.parseInt(tokens.nextToken());
int Aig = Integer.parseInt(tokens.nextToken());
int Aib = Integer.parseInt(tokens.nextToken());
dp[0][i] = Math.min(dp[1][i-1],dp[2][i-1]) + Air;
dp[1][i] = Math.min(dp[0][i-1],dp[2][i-1]) + Aig;
dp[2][i] = Math.min(dp[1][i-1],dp[0][i-1]) + Aib;
}
// 세팅
// 작업
int answer = Math.min(dp[0][N-1], dp[1][N-1]);
answer = Math.min(answer, dp[2][N-1]);
// 출력
// System.out.println("R: "+Arrays.toString(dp[0]));
// System.out.println("G: "+Arrays.toString(dp[1]));
// System.out.println("B: "+Arrays.toString(dp[2]));
System.out.println(answer);
}
}
[
12_084KB
|72 ms
]
원리 이해에 도움이 될까싶어서 DP테이블도 첨부합니다.