[java][boj][s3] 11727. 2×n 타일링 2

11727번: 2×n 타일링 2

문제

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

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

출력

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

풀이

2×n 타일링과 유사한 문제다 이번에는 2x2 타일이 추가되었는데, 이 타일은 짝수일 때와 홀수일 때가 다르게 추가된다고 생각하면 된다 사실 타일 생각은 안 해 보고 전부 노가다로 때려박았는데, 식을 적어 보니까 1, 3, 5, 11, 21, 43 순서로  DP[i] = DP[i-1] + 2*DP[i-2] 식이 나오게 된다 아마 짝수일 때와 홀수일 때가 다른 방식이 *2를 통해 적용되는 것 같다

코드

package A형대비;

import java.io.*;
import java.util.*;

public class s3_11727_2xn타일링2 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int[] num = new int[1001];
		
		num[0] = 1;
		num[1] = 3;
		
		for(int i = 2; i<N; i++) {
			num[i] = (num[i-1] + (num[i-2]*2))%10007;
		}
		
		System.out.println(num[N-1]);
	}
}

결과

 

#자바 #java #boj #백준 #알고리즘