[백준(Baekjoon)][자바(java)] 1904 : 01타일 / 동적 계획법 1

 

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

 

1904번: 01타일

 

* 풀이 방법

- 2진수의 길이에 따른 가짓수를 세어보니, 역시 피보나치 수열의 규칙이 나타남

 

n	cnt
1	1	1
2	2	00, 11
3	3	001, 100, 1114
4	5	0000, 0011, 1001, 1100, 1111
5	8	00001, 00100, 10000, 00111, 10011, 11001, 11100, 11111
6	13	000000, 000011, 001001, 100001, 001100, 100100, 110000, 111111, 001111, 100111, 110011, 111001, 1111000

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();

		int a = 0, b = 1, c = 0;
		for( int i = 1; i <= n; i++ ) {
			c = ( a + b ) % 15746;
			a = b;
			b = c;
		}

		System.out.println( c );
	}
}