N을 2a + 1b꼴로 만들어서 조합을 사용해서 수를 구하면 된다고 생각했는데 시간초과가 나왔다.. 겹치는 친구들이 있어서 점화식을 불가능하다고 생각했는데 검색해보니까 점화식이 되더라..? 왜 되는지 고민해 보았다.
시간초과 코드
import sys
from math import factorial
input = sys.stdin.readline
N = int(input())
def combi(n, r):
return factorial(n) // (factorial(r)*factorial(n-r))
def tile(n):
count = 0
for a in range(n//2 + 1): # 2*a + 1*b꼴, a는 0~n//2까지 가능
b = n - 2*a
count += combi(a+b, a)
return count
print(tile(N) % 15746)- 시간초과라 설명할 필요는 없지만..,, 전에 문제에서 조합은 내장함수 combinations를 쓰는 것보다 factorial을 사용해서 직접 식을 구하는 게 빨랐어서 이걸 썼다.
점화식으로 표현해보자
- n은 n-2번째 타일들에서 양옆에 00을 붙이거나, n-1번째 타일들에서 양옆에 1을 붙이면 된다.
- 그런데 이렇게 양옆에 이어붙이고 전체 경우의 수를 나열해보면 겹치는 친구들이 존재한다... 그렇다고 경우의 수를 저장해서 set에 넣을 수도 없는 노릇이고... 어캐 점화식이 되는 걸까..?
...고민을 며칠 해 보았는데,.,, 모르겠다...,, 점화식이란 걸 알고 나니까 보이긴 하는데 내가 첨부터 알아낼 수 있었을까..?
코드
import sys
from math import factorial
input = sys.stdin.readline
N = int(input())
tile = [0, 1, 2]
for i in range(3, N+1):
tile.append((tile[i-2] + tile[i-1]) % 15746)
print(tile[N])- 15746을 왜 나누나 했는데, N이 1000000까지 가능해서 가짓수가 int의 범위를 벗어나는 경우가 생길 수도 있기 때문이다.
결과
