본문 바로가기
문제풀이/백준

[JAVA] BOJ 백준 1149번 - RGB거리

by 그적 2023. 3. 27.

목차

  • 문제
  • 내가 푼 방법
  • 자바 코드
  • 결과 및 회고

1. 문제

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

 

1149번: RGB거리

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나

www.acmicpc.net


2. 내가 푼 방법

문제 설명이 뭔가 싶은데,, 결국 위 아래에 있는 집이 동일한 색상을 가지지 않으면 된다.

먼저 각 집의 색상을 칠할 때의 비용을 house 배열에 넣어주고, 비용의 최솟값을 담은 dp 배열을 생성해주었다.

 

나는 두 가지 함수를 만들었다.

- draw 함수 : N번째 집에서 최소 비용 찾기

- min 함수 : N번째 집에서 색을 칠하기 전, 가질 수 있는 최소 비용 찾기

 

핵심은 min 함수이기 때문에 잘 이해하도록 하자.

최소 비용을 담은 dp 배열이 채우기 위해 N번째 집에서 빨간색을 칠할 경우, N번째 집에서 초록색을 칠할 경우, N번째 집에서 파란색을 칠할 경우를 나눈다. 아래와 같은 점화식이 만들어지는 것을 찾아낸다.

N번째 집을 빨간색으로 칠하는 최소 비용 = N-1번째 집 최소 비용 (초록 or 파란) + 빨간색 비용

N번째 집을 초록색으로 칠하는 최소 비용 = N-1번째 집 최소 비용 (빨간 or 파란) + 초록색 비용

N번째 집을 파란색으로 칠하는 최소 비용 = N-1번째 집 최소 비용 (빨간 or 초록) + 파란색 비용

 

중요한 것은 Base-Condition이며, main문에서 0번째 집에서 빨간, 파란, 초록을 칠할 경우를 설정해 두는 것!


3. 자바 코드

import java.util.*;
import java.io.*;

class Main {
    static int N;
    static int[][] house;
    static int[][] dp;

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        house = new int[N][3];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            house[i][0] = Integer.parseInt(st.nextToken());
            house[i][1] = Integer.parseInt(st.nextToken());
            house[i][2] = Integer.parseInt(st.nextToken());
        }

        dp = new int[N][3];
        dp[0][0] = house[0][0];
        dp[0][1] = house[0][1];
        dp[0][2] = house[0][2];
        
        bw.write(draw(N-1)+"");

        br.close();
        bw.flush();
        bw.close();
    }

    public static int draw (int idx) {
        return Math.min(Math.min(min(idx, 0), min(idx, 1)), min(idx, 2));
    }

    public static int min (int idx, int rgb) {

        if (dp[idx][rgb] == 0) {
            if (rgb == 0) {
                dp[idx][rgb] = Math.min(min(idx-1, 1), min(idx-1, 2)) + house[idx][rgb];
            }
            else if (rgb == 1) {
                dp[idx][rgb] = Math.min(min(idx-1, 0), min(idx-1, 2)) + house[idx][rgb];
            }
            else if (rgb == 2) {
                dp[idx][rgb] = Math.min(min(idx-1, 0), min(idx-1, 1)) + house[idx][rgb];
            }
        }

        return dp[idx][rgb];
    }
}

4. 결과 및 회고

한 번쯤 풀어본 문제였는데,, 재귀로 풀었다가 실패하고 세 시간이나 걸렸다. ㅠㅠ 더 잘 찾아보자구.

 

댓글