[solved.ac 골드5] 1351_무한 수열 (파이썬, 재귀, 자료 구조, DP)

 

제한 사항

문제

무한 수열 A는 다음과 같다.

• A0 = 1
• Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)

N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 3개의 정수 N, P, Q가 주어진다.

출력

첫째 줄에 AN을 출력한다.

제한

 

 

 

예제

---

나의 풀이

이 문제는 메모리 제한이 상당히 빡빡하게 느껴졌다. 기존에 했던 DP 방식대로 메모이제이션(기록하면서 푸는 기법)하기 위해 리스트를 만들어서 문제를 풀이하려고 했다.

사실 메모리 제한에 걸리지 않았다면 절대 어렵지 않은 문제였다.

메모리 초과는 N + 1 크기로 만드는데 리스트를 만들었을 때 최대 크기가 10 ^ 12 + 1 이 된다. 아마 여기서 문제 풀이를 하기도 전에 리스트만 생성하고 메모리가 초과된 것이 아닌가 싶어서 리스트가 아닌 사전을 사용하기로 했다.

 

n, p, q = map(int, input().split())

d = {0: 1}

def rec_fun(start):
    if d.get(start) is not None: # 찾는 값이 이미 사전에 있는 경우
        return d[start]
    if d.get(start // p) is not None and d.get(start // q) is not None: # P로 나눈 값과 Q로 나눈 값이 사전에 있는 경우
        d[start] = d[start // p] + d[start // q] # 사전에 값을 저장
        return d[start]
    if d.get(start // p) is not None: # P로 나눈 값만 사전에 있는 경우
        return d[start // p] + rec_fun(start // q)
    if d.get(start // q) is not None: # Q로 나눈 값만 사전에 있는 경우
        return rec_fun(start // p) + d[start // q]
    else: # 둘 다 사전에 없는 경우
        return rec_fun(start // p) + rec_fun(start // q)

print(rec_fun(n))

 

d라는 사전이 있을 때 key가 start인 값을 얻기 위해서 두 가지 방법을 사용할 수 있다.

1. d[start]
2. d.get(start)

위 두 방법은 d에 start라는 key가 있을 때는 동일하게 값을 가져오지만 start라는 key가 없는 경우에 동작의 차이가 생긴다.

1. d[start] -> NameError 발생
2. d.get(start) -> None 리턴

나는 start가 d의 key 값에 있는지 확인하기 위해 if start in d.keys() 로 확인할 수도 있었지만 O(N)의 복잡도로 동작하기 때문에 d.get(start)를 사용해 key가 있는지 확인했다.

if d.get(start) is not None 으로 조건문을 수행하면 O(1)의 복잡도로 확인할 수 있다.

참고로 try ~ except 문을 사용하면 d[start]로도 확인할 수 있다.

 

사전에 key가 없는 경우 rec_fun()을 재귀적으로 수행해 값을 찾아 나간다.

만약 key가 있으면 해당 값을 반환하면 되고, P로 나눈 값과 Q로 나눈 값이 있다면 사전에 저장 후 반환하면 된다.

사전에 저장하지 않으면 메모이제이션 기법을 사용하지 않는 것이기 때문에 DP 풀이라고 할 수 없고 중복된 처리를 해야하므로 시간 초과가 발생할 것이다.

 

채점 결과