백준 - 2 x n 타일링

백준 -  2 x n 타일링

 

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

수학을 잘 못하는 필자는 위 문제를 완벽하게 풀이하는데 조금 시간이 걸렸다.

 

바로 풀이를 해보자. 

전형적인 DP문제이다. (DP : 동적 프로그래밍)

 

문제의 입력값이 1000까지 이므로 dp배열을 1001개를 생성한다.

 

n=1일 때 1 x 2 의 타일 하나만 사용 --> 1개 dp[1] = 1

 

n=2일 때 1 x 2의 타일 두개, 2 x 1의 타일 두개 --> 2개 dp[2] = 2

 

n=3일 때 맨 왼쪽에 1 x 2 가 있을 때 경우 --> 옆에 2 x 2 공간이 남고 이 공간은 n = 2일 때 값 + 맨 왼쪽에 2 x 1의 타일 두개가 있을 때 경우 --> 옆에 1 x 2 공간이 남고 이 공간은 n = 1 일 때 값

 

결국 d[3] = d[1] + d[2]라는 점화식이 도출된다.

 

이는 코드로 'd[n] = d[n-2] + d[n-1]'로 사용이 가능하고 피보나치 수열과 일치하는 것을 볼 수 있다.

 

이를 도형적으로 접근해보면, 맨 오른쪽 1 x 2가 있을 때 나머지 i-1공간 + 맨 오른쪽 2 x 1 가 두 개 있을 때 나머지 i-2공간이라고 할 수 있다. i-3부분은 확인하지 않는 이유는 이미 세었기 때문이다. 우리는 2 x 1, 1 x 2크기의 타일밖에 사용하지 못하므로 새로 추가되는 부분만 이 두 가지 경우를 신경써준다면 모든 경우를 다 세는 것과 같다.

 

10007로 나눈 이유는 문제에서 요구하기 때문이다. 아마 경우의 수가 커졌을 때를 대비해서 써놓은것 같다. 그런데 의문이 있다. 수행시간이 왜이렇게 오래 걸리는 걸까. 마지막 출력할 때 10007로 나누어보아도 똑같다. 흠.. 아무튼 정답처리는 받는 코드이다.

 

소스 코드로 확인하자.

n = int(input())

d = [0]*1001
d[1] = 1
d[2] = 2

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

print(d[n])