실버III. 백준1904 01타일

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

1904번: 01타일

 

주의 : if( N >= 2 ) 조건을 달지 않고 그냥 반복문으로 하니 100%에서 런타임에러가 났는데 이유를 모르겠음.

 

문제는 간단한데

00이 붙여질 조건과 1이 붙여질 조건이다.

1이 붙여질 조건은 앞선 d[n-1]개에 그냥 붙이면 되고 00의 경우 d[n-2]의 경우에서 붙여주면된다.

 

=> d[n] = d[n - 1] + d[n - 2]

 

import java.util.Scanner;

public class Q1904 {
	static int N;
	static long dp[];
	
	public static void main(String[] args) {
		solve();
	}
	
	
	public static void solve() {
		input();
		dp();
	}
	
	public static void input() {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		dp = new long[N + 1];
		sc.close();
	}
	
	
	public static void dp() {
		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]);
	}
}