풀이과정
이렇게 각 집마다 색깔을 겹치지 않게 색칠해줘야 한다.
그렇다면 2,2를 파랑으로 색칠할때 이미 최소값 계산이 다 되었다고 가정한 주황색중에 작은 값을 고른다.
(색이 겹치면 안되기 때문에 [1][2]는 제외시켰다.)
주황색중 작은 값을 파랑에 더하면 최소값이 나온다.
그렇다면 이걸 sudo코드로 바꾸자면 [2][2] += min([1][0], [1][1])이다.
맨 초반 고정값은 그대로 넣어주고 그 값을 토대로 각 배열의 최소값들을 식으로 표현한다면 사진과 같이 나온다.
맨 아래 나온 N번째 식을 점화식을 토대로 최소값을 구해준다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class backJoon1149 {
static int[][] house;
static int[][] dp;
final static int Red = 0;
final static int Green = 1;
final static int Blue = 2;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
house = new int[N][3];
dp = new int[N][3];
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine());
house[i][Red] = Integer.parseInt(st.nextToken());
house[i][Green] = Integer.parseInt(st.nextToken());
house[i][Blue] = Integer.parseInt(st.nextToken());
}
dp[0][Red] = house[0][Red];
dp[0][Green] = house[0][Green];
dp[0][Blue] = house[0][Blue];
System.out.println(Math.min(minCost(N-1, Red), Math.min(minCost(N-1, Green), minCost(N-1, Blue))));
}
public static int minCost(int N, int color) {
//아직 방문하지 않은 집 확인
if(dp[N][color] == 0) {
//저장한 값을 불러와 최소값 저장
if(color == Red) {
dp[N][Red] = Math.min(minCost(N-1, Green), minCost(N-1, Blue)) + house[N][Red];
}
else if(color == Green) {
dp[N][Green] = Math.min(minCost(N-1, Red), minCost(N-1, Blue)) + house[N][Green];
}
else {
dp[N][Blue] = Math.min(minCost(N-1, Red), minCost(N-1, Green)) + house[N][Blue];
}
}
return dp[N][color];
}
}
결과
dp에 저장된 최소값들도 출력해줬다. 이렇게 보면 더 이해하기 편할것이다.
'[BOJ]' 카테고리의 다른 글
[JAVA] 11725 트리의 부모 찾기 (0) | 2023.05.01 |
---|---|
[JAVA] 11726 2×n 타일링 (0) | 2023.04.14 |
[JAVA] 21939 문제 추천 시스템 Version 1 (0) | 2023.03.26 |
[JAVA] 11286 절대값 (0) | 2023.03.23 |
[JAVA] 4358 생태학 (0) | 2023.03.21 |