[BOJ-20544] 공룡게임(Java)

백준 20544 공룡게임

 

20544번: 공룡게임

 

문제 설명

 

 - 도현이는 공룡 게임을 이론상 무한히 플레이 할 수 있다.

 

 - 그렇기 때문에 규칙을 바꾸고 자긴이 깰 수 있는 맵의 가지수를 세보기로 했다.

 

 - 조건은 다음과 같다.

 

 - 맵의 길이는 N으로 주어지어 N개의 지점으러 이루어져있다.

 

 - 각 지점은 바닥이나 높이가 1 또는 2인 선인장(장애물)으로 이루어진다.

 

 - 시작 지점은 1이며, 공룡이 앞으로 갈수록 지점을 나타내는 수가 증가한다.

 

 - 공룡은 최대 2개의 인접한 선인장을 뛰어 넘을 수 있으며, 인접한 두 선인장의 높이의 합이 4이상이면 뛰어넘을 수 없다.

 

 - 시작 지점은 무조건 바닥이다.

 

 - 맵의 높이가 2인 선인장은 적어도 하나는 등장해야 한다,

 

 - 위 조건을 전부 만족하면서 선인장에 부딪히지 않고 상태가 바닥으로 고정된 가상의 N+1의 지점으로 도착하면 깰 수 있다고 정의한다.

 

 - 인접한 선인장이 존재하면 반드시 한 번에 뛰어넘어야 한다.

 

 - 꺨 수 있는 맵의 가짓수를 구해라.(단, 수가 너무 커질 수 있기 때문에 1,000,000,007로 나눈 나머지 값을 출력하라)

 

---

 

입력 값

 

 - 맵의 길이 N(1<=N<=1,000)이 주어진다.

---

 

 

예제

 

 

---

 

 

문제 분석

 

 - 이 문제에서 핵심적인 사항은 N+1번째 지점은 바닥이라는 것이다.

 

 - 즉, N+1번째 지점이 바닥이 될 수 있는 경우를 구하면 된다.

 

 - 또한, 높이가 2인 장애물은 반드시 나타나야 하기 때문에 이전까지 높이가 2인 장애물이 나왔는지, 나오지 않았는지도 저장해야 된다.

 

 - N번째 지점이 바닥인 경우는 세 가지로 구분할 수 있다.

   1. N-3번째 지점이 바닥이고, 2단 점프를 하는 경우

       => 이 경우는 3가지 경우의 수가 존재한다.(높이 조합 1, 1 / 1, 2 / 2, 1)

   2. N-2번째 지점이 바닥이고, 1단 점프를 하는 경우

       => 이 경우는 2가지 경우의 수가 존재한다.(높이 조합 1 / 2)

   3. N-1번째 지점이 바닥이고, 점프를 하지 앟는 경우

       => 이 경우는 1가지 경우의 수가 존재한다.

 

 - 다만 여기서 주의할 점은, N-3번째 지점이 바닥이고 2단 점프를 할 때 이전에 높이가 2인 장애물이 나오지 않았다면 1, 1 조합은 불가능해진다.

 

 - 똑같이, N-2번째 지점이 바닥인 경우 이전에 높이가 2인 장애물이 나오지 않았다면 1인 조합은 불가능해진다.

 

 - 이 것을 수식으로 정리해보자.

 

 - DP[i][0] = i번째가 바닥이고 이제까지 높이가 2인 장애물이 나오지 않은 경우

 

 - DP[i][1] = i번째가 바닥이고 이제까지 높이가 1인 장애물이 나온 경우

 

 - DP[i][0] = DP[i-1][0] + DP[i-2][0] + DP[i-3][0] 가 된다.

 

 - DP[i][1] = DP[i-1][1] + DP[i-2][0] + DP[i-2][1]*2 + DP[i-3][0]*2 + DP[i-3][1]*3 가 된다.

 

 - 즉, 처음부터 시작하여 DP[N+1][1]을 계산하여 리턴하면 된다.

 

 

---

 

 

소스 코드

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	/*
	dp[i][0] => i번째 땅인데 2가 하나도 없는 경우
	dp[i][1] => i번째 땅인데 2가 하나라도 나온 경우
	 */
	public static long dp[][] = new long[1002][2];
	public static void main(String[] args) throws IOException{

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(bf.readLine()) + 1;

		dp[0][0] = 0;
		dp[0][1] = 1;
		dp[1][0] = 1;
		dp[1][1] = 0;
		dp[2][0] = 1;
		dp[2][1] = 0;
		dp[3][0] = 2;
		dp[3][1] = 1;


		for(int i=4;i<=N;i++){
			dp[i][0] = dp[i-1][0] + dp[i-2][0] + dp[i-3][0];
			dp[i][0]%=1000000007;
			dp[i][1] = dp[i-1][1] + dp[i-2][0] + dp[i-2][1]*2 + dp[i-3][0]*2 + dp[i-3][1]*3;
			dp[i][1]%=1000000007;
		}
		System.out.println(dp[N][1]);

	}

}