백준 17404 RGB거리 2 [자바]

10 Jun 2022 in Develop / Solving

java

문제 분석

• N개의 집이 있다.
• i번째 집은 i-1, i+1번째 집과 색이 같지 않아야 한다.
• 각 집을 RGB로 칠하는데 드는 비용이 각각 주어진다.
• 모든 집을 칠하는 데에 드는 최솟값은?

입력조건

집의 수 N
N열에 걸쳐서 {
	R G B 로 칠하는 비용들
}

풀이과정

• dp인데, 조금 브루트포스 같은 dp
• 무슨 말이냐 하면, 1번 집을 R, G, B로 각각 칠할 때의 경우를 전부 dp로 계산함.
• 그래서 3차원 배열의 dp가 나오게 되고,
  집이 N개라면 N*3 *3 개의 배열을 생성하게 됨.
• 이렇게 구해진 수 들 중, 1번 집과 N번 집을 똑같게 칠하는 경우를 제외하고, 최솟값을 출력.

코드 구성

• dp

  int[][][] coloring = new int[N][3][3];
  for(int i = 0; i < 3; i++)
      for(int j = 0; j < 3; j++)
          coloring[1][i][j] = map[1][i] + map[0][j];
  for(int i = 0; i < 3; i++)
      coloring[1][i][i] = 2000000;
    
  // 2부터 N까지 내려가기
  for(int i = 2; i < N; i++) {
      for(int j = 0; j < 3; j++) {
          for(int k = 0; k < 3; k++) {
              coloring[i][j][k] = Math.min(coloring[i-1][(j+1)%3][k], coloring[i-1][(j+2)%3][k]) + map[i][j];					
          }
      }
  }
  

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BJ17404_RGB거리2 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int[][] map = new int[N][3];
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 0; j < 3; j++)
				map[i][j] = Integer.parseInt(st.nextToken());
		}
		// 입력 완료
		
		// R, G, B로 시작할 때 각각을 전부 계산.
		int[][][] coloring = new int[N][3][3];
		for(int i = 0; i < 3; i++)
			for(int j = 0; j < 3; j++)
				coloring[1][i][j] = map[1][i] + map[0][j];
		for(int i = 0; i < 3; i++)
			coloring[1][i][i] = 2000000;
		
		// 2부터 N까지 내려가기
		for(int i = 2; i < N; i++) {
			for(int j = 0; j < 3; j++) {
				for(int k = 0; k < 3; k++) {
					coloring[i][j][k] = Math.min(coloring[i-1][(j+1)%3][k], coloring[i-1][(j+2)%3][k]) + map[i][j];					
				}
			}
		}
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		for(int i = 0; i < 3; i++) {
			for(int j = 0; j < 3; j++) {
				if(i == j) continue;
				pq.add(coloring[N-1][i][j]);
			}
		}
		System.out.println(pq.poll());
	}
}