백준 17404번(JAVA)

반응형

골드이상의 DP문제는 3차원으로 DP배열을 구현해서 문제푸는것이 수월하다.

이 문제는 기존 RGB거리 문제에 조건을 하나 더 추가한것으로 2번째 인덱스에 첫번쨰집의 색깔을 지정해놓고 풀면된다.

기존 RGB문제와 3차원배열을 활용한 DP문제링크를 걸어둘테니 참고하면 이 문제를 푸는데 매우 도움이 될듯하다.

www.acmicpc.net/problem/1149

1149번: RGB거리

2021.05.08 - [백준 문제풀이(JAVA)/DP(다이나믹프로그래밍)] - 백준 1563번(JAVA)

백준 1563번(JAVA)

이 문제또한 3차원 배열을 활용하면 된다.Bottom-up방식을 사용했으며

dp[N][3][3]으로 3차원 dp를 선언해준다. 이 때 첫번째 인덱스는 몇번째집인지를 나타낸다.

2번째 인덱스는 첫번째집으로 어떤 색깔을 선택했는지 나타낸다. 마지막 3번째 인덱스는 N번째집의 색깔을 나타낸다.

예를들어 dp[3][1][2]이면 첫번째집은 초록색깔로 선택했고 4번째집(인덱스는 0부터시작이니깐)은 파랑색으로 칠할때의 드는 비용이다. 전체집을 색칠하는데 드는 비용의 최소값을 찾는게 목표다.

dp[3][1][2]=arr[3][2]+Math.min(dp[2][1][0],dp[2][1][1]), 이런 식으로 찾을 수 있다. for문으로 전체 dp배열을 채워주자.

 

 

소스코드

import java.util.*;
import java.io.*;
public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(br.readLine());
		int[][] arr=new int[N][3];
		int[][][] dp=new int[N][3][3];
		//첫번째 인덱스는 몇번째집인지,2번째는 첫번쨰집 색깔,3번째는 첫번째집 이외의 색깔을 의미
		String[] s;
		for(int i=0;i<N;i++)
		{
			s=br.readLine().split(" ");
			for(int j=0;j<3;j++)
			{
				arr[i][j]=Integer.parseInt(s[j]);
			}
		}
		dp[1][0][0]=Integer.MAX_VALUE;//첫째날에 빨강이면 둘째날은 빨강을 고르지 못한다.
		dp[1][0][1]=arr[0][0]+arr[1][1];
		dp[1][0][2]=arr[0][0]+arr[1][2];
		dp[1][1][1]=Integer.MAX_VALUE;//첫쨰날에 초록이면 둘쨰날은 초록을 고르지 못한다.
		dp[1][1][0]=arr[0][1]+arr[1][0];
		dp[1][1][2]=arr[0][1]+arr[1][2];
		dp[1][2][2]=Integer.MAX_VALUE;//첫째날에 파랑이면 둘쨰날은 파랑을 고르지 못한다.
		dp[1][2][0]=arr[0][2]+arr[1][0];
		dp[1][2][1]=arr[0][2]+arr[1][1];
		for(int i=2;i<N-1;i++)
		{
			for(int j=0;j<3;j++)
			{
				dp[i][j][0]=arr[i][0]+Math.min(dp[i-1][j][1],dp[i-1][j][2]);
				dp[i][j][1]=arr[i][1]+Math.min(dp[i-1][j][0],dp[i-1][j][2]);
				dp[i][j][2]=arr[i][2]+Math.min(dp[i-1][j][0],dp[i-1][j][1]);
			}
		}
		dp[N-1][0][0]=Integer.MAX_VALUE;
		dp[N-1][0][1]=arr[N-1][1]+Math.min(dp[N-2][0][0], dp[N-2][0][2]);
		dp[N-1][0][2]=arr[N-1][2]+Math.min(dp[N-2][0][0], dp[N-2][0][1]);
		dp[N-1][1][1]=Integer.MAX_VALUE;
		dp[N-1][1][0]=arr[N-1][0]+Math.min(dp[N-2][1][1], dp[N-2][1][2]);
		dp[N-1][1][2]=arr[N-1][2]+Math.min(dp[N-2][1][0], dp[N-2][1][1]);
		dp[N-1][2][2]=Integer.MAX_VALUE;
		dp[N-1][2][0]=arr[N-1][0]+Math.min(dp[N-2][2][1], dp[N-2][2][2]);
		dp[N-1][2][1]=arr[N-1][1]+Math.min(dp[N-2][2][0], dp[N-2][2][2]);
		int result=Integer.MAX_VALUE;
		for(int i=0;i<3;i++)
		{
			for(int j=0;j<3;j++)
			{
				
				result=Math.min(result, dp[N-1][i][j]);
			}
		}
		System.out.println(result);
	}
}

댓글과 지적은 언제든지 환영입니다~!

 

글이 마음에 들었다면 왼쪽이미지를 눌러서 후원 부탁드립니다><