알고리즘 - 백준 - 1149 - RGB거리

김성일·2024년 9월 5일
2

알고리즘

목록 보기
3/23
post-thumbnail

문제 바로가기

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

문제 소개

N개의 칸에 색을 칠할건데 이웃한 칸에 같은 색이 칠해지면 안된다
색은 세종류가 있고, 칸마다 그리고 색마다 색칠 비용이 다르다.
이때 모든 칸을 색칠하는 비용의 최소값을 구하시오.

어떻게 풀까? - 완전탐색

N개의 칸에 색 3개를 재료로 중복순열로 만들고 비용 다 계산해서 최소값을 찾자!
시간복잡도 = O(NX3^N) => O(1000X3^1000)
불가능.
아 어렵네.
어려우면 DP지.
DP를 의심해보자...

어떻게 풀까? - DP(군탈체포조 아님)

문제의 조건을 다시 보도록 하자.
"i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다."
뭔가 수열같은 느낌... 뭔가 점화식이랑 연관있어보이는 느낌...
점화식을 어떻게 만들지?
일반적으론 아래 같은 느낌으로 만드는데...

i번째 칸까지의 최소비용 = i-1번째까지의 최소값 + i번째의 최소값인 색의 값

앞에서부터 최소값인 색을 고를까?

그리고 다음 순서에서는 앞에서 쓴 색을 제외한 나머지 두색중에서 최소값인 색을 쓰자!
근데 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(디아루가 펄기아 아님) 테이블

원리 이해에 도움이 될까싶어서 DP테이블도 첨부합니다.

1번

2번

3번

4번

5번

profile
better을 통해 best로

0개의 댓글

관련 채용 정보