백준 1563번(JAVA)

3차원 DP로 해결하는 문제이다

골드 4이상부터는 대부분 3차원DP로 풀어야 하는 것 같다.

int[][][][ dp=new int[N][2][3];으로 선언해주고 [][][]에서 첫번째는 날짜를 2번째는 지각을 한 상태이면 1, 아니면0, 마지막인덱스는 연속결석날짜를 의미한다. dp[4][1][2]는 4번째날 지각을 한상태에서 2번연속 결석을한 경우의수를 의미한다.

일단 만약 날짜가 1일이면 지각,결석,출석 한가지씩이어서 3을 출력하고 시스템종료

그다음 2틀째날에는 총 8가지 경우의수가 있다. 각각 맞게 설정해주고 

bottom-up방식으로 구현하기 위해 for문을 i=2부터 실행해준다.

자세한 사항은 아래 소스코드를 보며 이해하자.

 

소스코드

import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int[][][] dp=new int[N][2][3];//2번쨰 인덱스는 지각을했는지안했는지,3번째인덱스는 연속결석수
        //2번째 인덱스가 1이면 지각을 이미 한 번 한 상태라는 뜻이다.
		if(N==1)//첫째날에는 지각,결석,출석 한가지씩 총 3가지
		{
			System.out.println("3");
			System.exit(0);
		}
		dp[1][0][0]=2;//출출,결출
		dp[1][0][1]=1;//출결
		dp[1][0][2]=1;//결결
		dp[1][1][0]=3;//지출,출지,결지
		dp[1][1][1]=1;//지결
		dp[1][1][2]=0;//2일로는 불가능한 조합이다
		for(int i=2;i<N;i++)
		{
			dp[i][0][0]=(dp[i-1][0][0]+dp[i-1][0][1]+dp[i-1][0][2])%1000000;
			dp[i][0][1]=dp[i-1][0][0];
			dp[i][0][2]=dp[i-1][0][1];//i번째날이 2연속 결속이려면 i-1번째날은 결석이어야 한다.
			dp[i][1][0]=(dp[i-1][1][0]+dp[i-1][1][1]+dp[i-1][1][2]+dp[i-1][0][0]+dp[i-1][0][1]+dp[i-1][0][2])%1000000;
            //지각을 안한상태인 i-1번째날을 지각을 한상태인 i번쨰날에 더해준다.
			dp[i][1][1]=dp[i-1][1][0];
			dp[i][1][2]=dp[i-1][1][1];
		}
		long sum=0;
		for(int i=0;i<3;i++)
		{
			sum+=dp[N-1][0][i];
			sum+=dp[N-1][1][i];
		}
		System.out.println(sum%1000000);
		

	}

}

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

 

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