[1904]01타일 풀이

문제 : https://www.acmicpc.net/problem/1904

 

풀이과정:

N = int(input())

fibo_value = [-1]*(N + 1)

def fibonacci(n):
    if fibo_value[n] != -1:
        return fibo_value[n]
    if n == 1:
        fibo_value[1] = 1
        return 1
    if n == 2:
        fibo_value[2] = 2
        return 2
    else:
        fibo_value[n] = fibonacci(n-2) + fibonacci(n-1)
        return fibo_value[n]

print(fibonacci(N) % 15746)

고민하다가 피보나치 수열 문제라는 것을 알고 코드를 위처럼 짰으나.. 런타임 에러가 났다. 찾아보니 재귀함수가 너무 깊어져도 런타임 에러가 난다고 한다. 나는 iteration을 이용하여 풀기로 하였다.

 

N = int(input())

first, second = 1, 2

for i in range(1, N):
    first, second = second % 15746, (first + second) % 15746
    
print(first)

결과적으로 다른 사람의 코드를 본게 이 문제를 해결하는데 도움이 되었다. 배열을 생성하여 메모이제이션을 이용하려 풀려 했는데 메모리 초과 문제가 생겼다. 어떻게 풀지 고민하다가 다른 사람이 한 걸 통해 풀이방법을 알아내어 작성하였다. 변수를 두 개만 사용하여 피보나치 수열을 알아내는 혁신적인 방법이었다. 작성한거까진 좋았는데 그 과정에서도 시간 초과 문제가 생겼다. 마지막 줄 print문에서 한번 나머지를 구하려 하지 않고 for문 반복 과정에서 15746를 계속 나눠주도록 하였다. 결국 문제를 해결하였다. 하지만 스스로 해결하지 못해서 씁쓸하다...

 

엄청나게 커지는 수를 더하는 것보다 지속적으로 수를 나머지 연산자로 크기를 줄여주는게 시간을 줄일 수 있다는 사실을 알 수 있었다.