백준 1351번 - 무한 수열(★★★ / O / 1) : Python

개요

• 풀이 시간 : 20분
• 시간 제한 : 2초
• 메모리 제한 : 128 MB
• 기출 : baekjoon
• 난이도 : 골드 4
• 링크 : https://www.acmicpc.net/problem/1351

문제

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

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

N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오. 참고로 ⌊x⌋는 x를 넘지 않는 가장 큰 정수이다.

입력

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

출력

첫째 줄에 AN을 출력한다.

제한

• 0 ≤ N ≤ 10^12
• 2 ≤ P, Q ≤ 10^9

해결방법

문제 이해하기

일단 문제를 읽는 순간 거부감이 있었다. 딱봐도 다이나믹을 써야할거 같은 느낌적인 느낌. 기분적인 기분이랄까...

알고리즘

다행히도 해당 패턴은 내가 수차례 경험해본 적이 있었기 때문에 쉽게 풀 수 있었다. 바로 DFS + 다이나믹프로그래밍 방식이다. 백준 1563번 - 개근상 문제랑 형식은 거의 동일하다고 볼 수 있겠네. 다만 이 문제는 더 쉬운 편에 속한다.

하지만 약간 문제가 있었다면 바로 N이 너무 커서 이것을 dp 테이블에 전부 다 담지 못한다는 것이다. 그래서 굳이 list로 만들필요없이 dict으로 만들어봤다. 이것이 이번 문제 핵심.

Python

내 코드

from collections import defaultdict
import sys
input = sys.stdin.readline


def dfs(n):
    if data[n] != 0:
        return data[n]

    data[n] = dfs(n // p) + dfs(n // q)
    return data[n]


if __name__ == "__main__":
    n, p, q = map(int, input().split())
    data = defaultdict(int)
    data[0] = 1

    # print(data[0], data[1])
    print(dfs(n))

사실 코드가 너무 단순했기 때문에 이게 맞을까? 라는 의심이 있었다. 하지만 그것은 기우였다. 다른 코드도 살펴보니 역시 DFS(재귀)방식과 dict형을 사용해서 풀었더라고. 다만 defaultdict을 여기서는 안쓰고 구현하는게 더 속도랑 메모리 측면에서 빠른 편인거 같더라...

💻 참고 : https://www.acmicpc.net/source/26416749

✍️ 이번 문제는 이전에도 많이 봐오던 유형이기 때문에 쉽게 풀 수 있었던거 같다. 꾸준히 노력한 결과라고 볼 수 있겠다