문제

백준 2×n 타일링 2 문제 보러가기



문제점 해결

프로그래머스에 있는 2×n 타일링 문제와 비슷한 유형이었다. 다만 이 문제엔 2×2 타일이 존재한다는 차이가 있다. 아래 표를 보면 3개의 타일로 채우는 방법일 때, n-2의 방법의 수를 더한 값과 같아짐을 알 수 있다.

n 2×1, 1×2 2×1, 1×2, 2×2
1 1가지 1가지
2 2가지 3가지
3 3가지 5가지
4 5가지 11가지

즉, 3개의 타일로 채우는 방법의 수는 (n-1) + (n-2) + (n-2)이라는 규칙을 찾아 낼 수 있다.



풀이

import java.util.Scanner;

public class Main {
	static int[] memo;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		memo = new int[1001];
		memo[0] = 1;
		System.out.println(fibo(n) % 10007);
	}
	
	static int fibo(int n) {
		if(n <= 1) return n;
		memo[n-1] = fibo(n-1);
		return memo[n-1] % 10007 + memo[n-2] % 10007 + memo[n-2] % 10007;
	}
}