[Algorithm] 1351. 무한수열

1351: 무한수열

https://www.acmicpc.net/problem/1351

• 문제 티어 : G5
• 풀이 여부 : Solved
• 소요 시간 : 20:33

정답 코드

시간복잡도 : O(logN)

import sys
input = sys.stdin.readline

N, P, Q = map(int, input().rstrip().split())
memo = {0:1}

def find_A(n):
  if n in memo:
    return memo[n]
  else:
    memo[n] = find_A(n//P) + find_A(n//Q)
    return memo[n]

print(find_A(N))

접근 방식

탑다운으로 필요한 부분만을 메모이제이션으로 계산해서 사용하기

접근 시행착오(+ 코드)

시간 복잡도 : O(N)

# 메모리초과
import sys, math
input = sys.stdin.readline

N, P, Q = map(int, input().rstrip().split())
memo = {0: 1}
memo[1] = memo[0] + memo[0]

for i in range(2, N+1):
  if i not in memo:
    memo[i] = memo[math.floor(i//P)] + memo[math.floor(i//Q)]
print(memo[N])

배운점 또는 느낀점

바텀업보다 탑다운이 효율적인 해결 방안이 될 수 있음을 깨달은 문제다!