목차
- 문제
- 내가 푼 방법
- 자바 코드
- 결과 및 회고
1. 문제
https://www.acmicpc.net/problem/1149
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. 결과 및 회고
한 번쯤 풀어본 문제였는데,, 재귀로 풀었다가 실패하고 세 시간이나 걸렸다. ㅠㅠ 더 잘 찾아보자구.
'문제풀이 > 백준' 카테고리의 다른 글
[JAVA] BOJ 백준 22862번 - 가장 긴 짝수 연속한 부분 수열 (large) (0) | 2023.05.13 |
---|---|
[JAVA] BOJ 백준 13144번 - List of Unique Numbers (0) | 2023.05.12 |
[JAVA] BOJ 백준 2579번 - 계단 오르기 (0) | 2023.03.27 |
[JAVA] BOJ 백준 2206번 - 벽 부수고 이동하기 (0) | 2023.02.14 |
[JAVA] BOJ 백준 11003번 - 최솟값 찾기 (0) | 2023.02.14 |
댓글