11726

날짜 : 2022. 11. 02

사용 언어 : python

 

문제

 

 

코드

import sys
a = [0] * 1001
a[1] = 1
a[2] = 2
a[3] = 3
for i in range(3, len(a)):
    a[i] = a[i-1] + a[i-2]
n = int(sys.stdin.readline())
print(a[n] % 10007)

 

 

알게된 점

- 맨 처음 어떻게 접근해야 할 지 몰라 가로길이를 기준으로 4의 경우 1 + 3, 3 + 1, 2 + 2의 경우의 수를 더한 후 겹치는 부분을 제외하는 방식으로 풀이하는 방향으로 잡았는데 너무 비효율적이었다.

- 그래서 다른 풀이를 찾아보니 맨 뒤에 2 x 1 블록을 붙이는 경우와 2 x 1 블록 2개를 붙이는 경우 총 2가지 케이스를 서로 더함으로써 문제를 해결하는 것을 보았다.

- 2 x 1 블록만을 더하는 경우에는 앞전에 있는 가로길이 (n-1)의 경우의 수가 해당될 것이고

- 2 x 2 블록 2개를 더하는 경우에는 앞전에 있는 가로길이 (n-2)의 경우의 수가 해당된다.

- 겹치는 부분또한 없기 때문에 점화식은 d[n] = d[n-1] + d[n-2]가 도출된다.

- 겹치는 부분을 줄이는 과정에서 어떻게 해야 효율적인지를 고민하느라 많은 시간을 할애한 것 같다.

 

 

참고 사이트

- https://yabmoons.tistory.com/506

[ 백준 11726 ] 2xn 타일링 (C++)