[백준] 11727번 : 2×n 타일링 2 with python3, java

22 Aug 2018

Reading time ~1 minute

문제 : https://www.acmicpc.net/problem/11727

목표:

2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 10,007로 나눈 나머지를 출력

조건:

1 ≤ n ≤ 1,000
O(N**3)가능

solution 설명 :

점화식 : d[i] = d[i-1] + 2*d[i-2]

d[i-2]에 2를 곱한 이유는 i가 될 수 있는 i-2날 때 아래와 같이 두가지
because-multiple-2

d[3]과 d[5]로 보면
아래와 같이 되기 때문에 2를 곱하는 것이다

why-multiple-2

N = int(input())
d = [0] * (N+1)

d[1] = 1
d[2] = 3
for i in range(3, N+1):
    d[i] = (d[i-1] + 2*d[i-2]) % 10007
print(d[N]% 10007)

import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), a, b=1, res=1;

		for(int i=0;i<n-1;i++){
			a=b;
			b=res;
			res=(2*a+b)%10007;
		}
		System.out.println(res);
	}
}

algorithm 백준