1904

날짜 : 2022. 10. 29

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())
f = [1] * (n+1)

for i in range(2, n+1):
    f[i] = (f[i-1] + f[i-2]) % 15746
print(f[n])

 

시간초과 코드

import sys
import math

n = int(sys.stdin.readline())
cnt = 0

for i in range(0, n+1): # b의 개수
    if (n-i) % 2 != 0:
        continue
    j = (n - i) // 2 # a의 개수
    cnt += math.factorial(i+j) / (math.factorial(i) * math.factorial(j))

print(int(cnt % 15746))

 

알게된 점

- 타일 00을 A, 타일 1을 B로 치환하여 n값에 따라 배열하는 방식으로 문제를 풀었지만 당연하게도(?) 시간초과가 나왔다.

- 아마 중간에 들어있는 팩토리얼 연산 때문이었던 것 같다.

- 그래서 직접 그려서 고민해보니까 f[n] = f[n-1] + f[n-2]라는 결과를 알 수 있었다.

- 타일을 n개 사용하는 경우 (n-1)개 사용한 경우에 타일 1을 추가한 케이스와 (n-2)개 사용한 경우에 타일 00을 추가한 케이스를 더하면 되기 때문이다. 그래서 위와 같은 점화식이 나왔고 for문으로 단순하게 구현할 수 있었다.

 

 

참고 사이트

- https://sungmin-joo.tistory.com/21

[백준] 1904번 01타일 파이썬 해설