백준 11727번 - 2×n 타일링 2(Python)

2*n 넓이의 직사각형을 2*1과 2*2 넓이의 직사각형(정사각형 또한 직사각형이다)으로 채우는 문제이다. 

 

설명처럼 문제가 요구하는 것도 굉장히 간단하다. 

타일의 가로(편의상) 길이를 입력받은 후 그를 채울 수 있는 경우의 수를 계산하여 출력하는 것이 문제의 전부이다. 

2*1일 때

n이 1일 때는 경우의 수가 하나뿐이다(2*1).

 

2*2일 때

n이 2일 때는 경우의 수가 3개이다.

 

2*3일 때

n이 3일 때는 경우의 수가 위처럼 5개이고 

 

2*4일 때

n이 4일 때는 경우의 수가 위처럼 11개 인데 

그렇다면 이 수들 간의 규칙성을 찾아야 하지 않을까? 하는 생각을 가장 먼저 했다.

1) 1

2) 3

3) 5

4) 11

에서 

5 = 1*2 + 3 이다.

그리고 11 = 3*2 + 5 이다.

이걸 수식으로 표현하면 f(n) = f(n-1) + f(n-2) * 2 로 나타낼 수 있다. 

-> 이런 방식으로 이전의 값을 활용해서 다음의 값을 구하는 것이 다이나믹 프로그래밍! 

 

 

이제 코드

a = int(input())

t = [0] * 1001		# n이 1일 때부터 배열(인덱스 1~)에 저장
t[1] = 1 			# n = 1 일 때 
t[2] = 3			# n = 2 일 때 

for i in range(3, a+1):		# n = 3 이상일 때 <- 계산해서 배열에 대입 
    t[i] = (t[i-1] + t[i-2] * 2) 
 
print(t[a]% 10007) 			# 출력 조건: 10007로 나눈 값 출력

첫 줄에서 n 값을 입력받은 후, t[3]부터 반복문을 활용해서 기존의 t[1], t[2] 값을 이용하여 차례대로 t[n] 값까지 계산한 값을 t[n]에 대입한다. (for 문까지의 내용) 

그리고 명시되어 있는 출력 조건인 10007로 이를 나눈 수를 출력해주면 끝이다. 

간단한 문제! 

뭔가 코딩할 때도 수학적 센스가 필요하다는 걸 느낀다 가끔... 끝!