[Java] 백준 1904번 01타일

https://www.acmicpc.net/problem/1904

1904번: 01타일

문제 설명

• 1과 00 타일로 크기가 N인 2진 수열을 만들 수 있는 가짓수
• N은 N ≤ 1,000,00인 자연수

dp [N]은 크기가 N인 2진 수열을 만들 수 있는 가지 수라고 하자.

N=1부터 경우의 수를 생각해보자.

 

dp [1] = 1 (1)

dp [2] = 2 (11, 00)

dp [3] = 3 (111, 100, 001) -> 00 타일은 0 두 개가 붙어 있으므로 000은 만들 수 없다

dp [4] = 5 (1111, 1001, 1100, 0011, 0000) 

dp [5] = 8 (11111, 00111, 00001, 00100, 10011, 10000, 11001, 11100)

...

 

위 경우의 수를 보면 

dp [N] = dp [N-1]+dp [N-2]

라는 규칙을 찾을 수 있다.

 

주의할 점! 

N은 자연수이므로 무조건 1보다 크거나 같은 수이다.

따라서 dp [0]과 dp [1]은 초기화해주고 for문 시작 전 N>=2 일 때의 조건을 걸어주어야 런타임 에러가 발생하지 않는다.

import java.util.Scanner;

public class Main {
	public static void main(String[] args ) {
		
		Scanner s= new Scanner(System.in);
		
		int N = s.nextInt();
		int dp[] = new int[N+1];
		
        //초기화
		dp[0]=1; 
		dp[1]=1;
		
		
		if(N>=2) {
			for(int i=2;i<=N;i++) {
				dp[i]=(dp[i-1] + dp[i-2])% 15746;
			}
		}
		
		System.out.println(dp[N]);
	}
}