백준 1904번_01 타일 [python/파이썬]

# 정답 풀이

def tile(n):
    result = 0
    temp1 = 1
    temp2 = 2
    for i in range(1, n + 1):
        if i == 1:
            result = temp1
        elif i == 2:
            result = temp2
        else:
            result = temp1 + temp2
            temp1 = temp2 % 15746
            temp2 = result % 15746
 
    return result % 15746
 
num = int(input())
print(tile(num))

 

 N을 1부터 차례대로 구해보면 피보나치와 같은 점화식이 나오는 것을 확인할 수 있다. 이 때 N이 커질 경우 결과값이 정수범위를 초과하는데 이를 방지하기 위해 15746으로 구한 나머지를 저장한다. 나머지를 미리 구한 뒤 계산을 해도 결과값에는 차이가 없다.

 

 

# 번외 풀이 (시간 초과)

1 2 3 4 5 6 7 8 9 10 11

from math import factorial num = int(input())   result = 0 for i in range(num//2 + 1):     zero_cnt = i     one_cnt = num-(2*i)     result += factorial(num-i) // (factorial(i) * factorial(num-2*i))   print(result%15746)   Colored by Color Scripter

cs

 

 위의 코드는 시간 초과로 틀린 코드이지만 N의 값이 크지 않다면 같은 결과를 보여준다. 정답 코드가 점화식을 이용한 코드 였다면 번외 코드는 조합을 이용한 코드이다. 선택되는 0과 1의 개수를 조합하여 같은 결과를 얻을 수 있다.