[백준 *Java] - RGB거리2 (17404)
17404번: RGB거리 2
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
문제 설명
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
1. 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
2. N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
3. i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.
입력
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
👇 접근방식 (내 생각보기)
기존에 풀었던 RGB거리 문제에서 조건이 하나 더 붙었습니다.
1번집과 N번집은 색이 같으면 안된다는 조건입니다.
처음에 생각한 방식은, 미리 지정을 하면 어떨까? 라는 생각을 했습니다.
미리 지정을 하지만, 이걸 어떻게 점화식으로 풀어나가야할까라고 생각했는데 점화식 설계를 하지 못했습니다..
다른 분 코드를 보고 난 뒤에, 놓치고 있던 부분이 있었습니다.
기존 RGB거리 로직에,
1번 집의 색을 고정시키기 위해서 다른 색을 절대 선택되지 않도록 최대의 값으로 세팅을 해주고 기존 RGB 구하시는 방법대로 구하면 된다. 문제에서 집의 수 N이 최대 1000개이며, 칠하는 비용이 1,000 보다 작거나 같은 자연수라 하여, 최대 비용 값음 1000 * 1000 즉, 100만이 됩니다. 그래서 1,000,001 로 첫번 째에 칠하는 색 제외한 색을 최소값이 안되도록 최대값 1,000,001 로 초기화합니다.
예를 들어, 1번 집의 색을 R로 정해 놓는다면, G와 B는 절대 선택되지 못하도록 1번 집의 G와 B의 비용을 최대값으로 초기화를 시킨다.
아래는 위의 설명대로 짠 코드입니다.
import java.io.*;
import java.util.StringTokenizer;
public class Main{
static int[][] DP;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
DP = new int[1001][3];
int [][] arr = new int[1001][3];
int N = Integer.parseInt(br.readLine());
StringTokenizer st;
// 우선 원래 배열 초기화
for(int i = 0; i < N; i++){
st = new StringTokenizer(br.readLine());
for(int j = 0; j < 3; j++){
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
int min = Integer.MAX_VALUE;
// 0번째 집을 어떤색으로 칠하느냐에 따라 각각 최소값을 구할 수 있으니 3번 반복
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
if(i == j) DP[0][j] = arr[0][i]; // 0 번째 집을 현재 i 값과 같을 때, 배열값 세팅합니다.
else DP[0][j] = 1000 * 1000 + 1; // 최대 1,000,001 을 넘지 않습니다. // 나머지는 최소 비용이 나올 수 없는 값으로 초기화 한다.
}
// 반복문을 통해 모든 집을 칠하는 경우를 구해나간다.
for(int j = 1; j < N; j++){
DP[j][0] = Math.min(DP[j-1][1], DP[j-1][2]) + arr[j][0];
DP[j][1] = Math.min(DP[j-1][0], DP[j-1][2]) + arr[j][1];
DP[j][2] = Math.min(DP[j-1][0], DP[j-1][1]) + arr[j][2];
}
// n-1번째까지 구해진 값 중 최소 비용의 값을 구한다.
for(int j = 0; j < 3; j++) {
if(i == j) continue;
min = Math.min(min, DP[N-1][j]);
}
}
System.out.println(min);
}
}
위 코드 주석 외에 추가로 설명을하자면, 아래 사진을 통하여 예제 입력4가 어떻게 값이 세팅되는지 확인하실 수 있습니다.
