[백준] 1904번 01타일 자바

문제

 

1904번: 01타일

 

 

문제 풀이

 

N의 증가에 따라 결과값을 잘 생각해봐야 dp임을 알 수 있다. 

N=1의 경우, 1       -> 1

N=2의 경우, 00, 11  -> 2

N=3의 경우, 001, 100, 111 -> 3

N=4의 경우, 0011, 0000, 1001, 1100, 1111 -> 5

....

쭉 보면 N(i) = N(i-1) + N(i-2) 의 점화식으로 도출할 수 있다.

그 이유는 짝수개일 때와 홀수 개일 때 00 또는 1을 붙여서 가져오면 되기 때문이다.

 

 

소스 코드

 

public class b_1904 {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		if(N == 1) {
			System.out.println("1");
			return;
		}
		
		if(N == 2) {
			System.out.println("2");
			return;
		}
		
		int[] dp = new int[N+1];
		dp[1] = 1;
		dp[2] = 2;
		
		for(int i = 3; i <= N; i++) {
			dp[i] = dp[i-1] + dp[i-2];
			dp[i] %= 15746;
		}
		
		System.out.println(dp[N]);
	}

}