BOJ1351. 무한 수열

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

  • 문제를 보자마자 MOD가 없는것을 보고 한껏 쫄아서 파이썬으로 일단 풀어봤다.
  • 최대값이 나올만한 입력을 넣었는데도 출력값이 long long 이하인 것은 매우 신기함. 오 역시 나누기의 위력
  • C++로 다시풀었더니 졸라 빠르다. 역시 Native의 위대함.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
LL N, P, Q;
unordered_map<LL, LL> dp;

LL go(LL n) {
  if(n == 0) return 1;
  if(dp.count(n)) return dp[n];
  return dp[n] = go(n/P) + go(n/Q);
}

int main() {
  cin >> N >> P >> Q;
  cout << go(N);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import sys

N,P,Q = (int(x) for x in input().split())
dp = {}

def go(n):
    if n == 0 :
        return 1;
    if n in dp:
        return dp[n]
    dp[n] = go(n//P) + go(n//Q)
    return dp[n]

print(go(N))