728x90
반응형
※ 문제링크
해당 문제는 피보나치 수열을 사용해서 풀어야하는 문제였다. 그래서 처음에는 피보나치 수열 함수를 작성하고 메모이제이션 방식을 활용하여 풀어보았는데, 시간초과가 발생하여 코드를 보다 더 간단하게 작성해보았다. 추가적으로 해당문제는 범위가 크기때문에 문제에서 주어진 숫자인 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 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.
728x90
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 1932번 정수 삼각형 / 사용언어 : 파이썬(python) (0) | 2021.12.22 |
---|---|
[BOJ] 9461번 파도반 수열 / 사용언어 : 파이썬(python) (0) | 2021.12.22 |
[BOJ] 9184번 신나는 함수 실행 / 사용언어 : 파이썬(python) (0) | 2021.12.22 |
[BOJ] 1003번 피보나치 함수 / 사용언어 : 파이썬(python) (0) | 2021.12.22 |
[BOJ] 2004번 조합 0의 개수 / 사용언어 : 파이썬(python) (0) | 2021.12.22 |
댓글