Baekjoon/[3] DP

[백준] 1149번 RGB거리 JAVA (자바) 풀이

Poorm 푸름 2024. 8. 8. 17:55

문제 1149번 (DP)

 :  RGB거리에는 집이 N개 있다

   집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다

   모든 집을 칠하는 비용의 최솟값을 구해보자.

 

 :  규칙

  • 2번 집의 색 ≠ 1, 3번 집의 색
  • i(2 ≤ i ≤ N-1)번 집의 색 ≠  i-1번, i+1번 집의 색

 

 

[입력]


 :  첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)

 :  둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다

    (집을 칠하는 비용은 1,000보다 작거나 같은 자연수)

 

 

[출력]

 

 :   첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력

 


[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

탑다운 (Top-Down)  보텀업 (Bottom-Up)
작은 크기로 문제를 나눠서 해결 작은 것부터 해결해서 점차 빌드업
메모제이션 (memoization) 타뷸레이션 (tabulation)
일부만 계산해도 답이 나올 때 모두 계산해야 답이 나올 때
재귀 반복문
시간 복잡도 O(n) 시간 복잡도 O(n)

 

1. dp 규칙 찾기

  • 이전의 값을 통해 현재의 값 힌트를 얻는다!
    • dp[n]을 구하기 위해서는 dp[n-1]의 값을 살펴보아야 한다
    • 고로 dp[1][0] = Math.min(dp[0][1],dp[0][2])+cost[1][0]
    • 1번째 집의 색이 R이라면 이전 집의 색은 G 또는 B이다
    • 이중에 최소값을 구하고 현재 색의 비용을 더해준다

 

 

 [코드]

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

 

 

 [해설]
     

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int arr[][] = new int[N][3];  R / G / B 배열
        
 :  for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][0]=Integer.parseInt(st.nextToken());  R
            arr[i][1]=Integer.parseInt(st.nextToken());  G
            arr[i][2]=Integer.parseInt(st.nextToken());  B
    }
        
 :  int dp[][] = new int[N][3];  dp 생성
    dp[0][0] = arr[0][0];  맨처음 R 초기화
    dp[0][1] = arr[0][1];  맨처음 G 초기화 
    dp[0][2] = arr[0][2];  맨처음 B 초기화
        
 :  for(int i=1;i<N;i++){
            dp[i][0]=Math.min(dp[i-1][1],dp[i-1][2])+arr[i][0];  이전 집 색(G/B)의 최소비용 + 현재 색 비용(R)
            dp[i][1]=Math.min(dp[i-1][0],dp[i-1][2])+arr[i][1];  이전 집 색(R/B)의 최소비용 + 현재 색 비용(G)
            dp[i][2]=Math.min(dp[i-1][0],dp[i-1][1])+arr[i][2];  이전 집 색(R/G)의 최소비용 + 현재 색 비용(B)
    }
       

 :  System.out.println(Math.min(dp[N-1][0],Math.min(dp[N-1][1],dp[N-1][2])));  모든 R/G/B의 최소비용 출력
 
    

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

 

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

 

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

저작자표시