[백준] 11726번 2 x n 타일링 자바 풀이

문제

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초

256 MB

166553

64421

47778

36.624%

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

풀이

아래처럼 실제로 직사각형을 채우는 방법을 나열 해본 후 n번째 직사각형을 채우는 방법은 n-1번째와 n-2번째의 합이라는 것을 알 수 있었다.

이 후 방법의 수를 10,007로 나누어 출력해줬다.

1 - 1
1

2 - 2
1 1
2 2

3 - 3
1 1 1
1 2 2
2 2 1

4 - 5
1 1 1 1
1 2 2 1
2 2 1 1
1 1 2 2
2 2 2 2

5 - 8  
1 1 1 1 1
1 2 2 1 1
2 2 1 1 1
1 1 2 2 1
2 2 2 2 1
1 1 1 2 2
1 2 2 2 2
2 2 1 2 2

 

코드

package com.company.baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B11726 {
	static long[] dp = new long[1001];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());

		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 3;
		for (int i = 4; i <= n; i++) {
			dp[i] = (dp[i-1] % 10007) + (dp[i-2] % 10007);
		}

		System.out.println(dp[n] % 10007);
	}
}