[BOJ] 1904번 타일 / 사용언어 : 파이썬(python)

※ 문제링크

1904번: 01타일

해당 문제는 피보나치 수열을 사용해서 풀어야하는 문제였다. 그래서 처음에는 피보나치 수열 함수를 작성하고 메모이제이션 방식을 활용하여 풀어보았는데, 시간초과가 발생하여 코드를 보다 더 간단하게 작성해보았다. 추가적으로 해당문제는 범위가 크기때문에 문제에서 주어진 숫자인 15746으로 나누어서 값을 저장하지 않으면 오버플로우 문제가발생할 수 있다. 그러므로 반드시 값을 저장할 때는 원래값이 아닌 나머지 값들을 저장해주어야 했다. 문제를 푸는 데 사용한 방법과 코드는 아래와 같다.

1. N+1개의 개수로 이루어진 리스트를 만든다.

2. 피보나치수열 규칙을 가지는 문제임을 활용하여 N까지 반복문을 돌려 결과값을 구한다.

+ Top-down 방식으로 값을 출력하려고 하면 Maxdepth를 초과하는 문제가 발생하므로 바텀업 방식을 사용했다.

 

# 1 (1) 
# 00 11 (2) 
# 001 111 100 (3)
# 0000 0011 1100 1111 1001 (5)
# 00001 00100 10000 00111 11001 11100 10011 11111 (8)

# 결과값 출력에는 문제가 없으나 시간초과가 발생하는 코드
fibo_memo = {}
def fibo(number):
    if number == 0:
        fibo_memo[number] = (1 % 15746)
    if number == 1:
        fibo_memo[number] = (1 % 15746)
    if number not in fibo_memo:
        check = 2
        while True:
            if check > number:
                break
            fibo_memo[check] = (fibo(check-1) + fibo(check-2)) % 15746
            check += 1
    return fibo_memo[number]
            
N = int(input())
print(fibo(N))

# 시간초과 문제로 코드를 보다 간단하게 수정한 코드(원리는 동일)
arr = [1 for _ in range(N+1)]
for i in range(2, N+1):
    arr[i] = (arr[i-1] + arr[i-2]) % 15746 
print(arr[N])

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.