190326 BOJ 1351번 무한 수열

메모이제이션

- 그냥 규칙 찾아서 재귀를 때려박으니 시간 초과가 났다

- 디버깅을 하다 보니 반복되는 값이 보여서 메모이제이션을 활용해 통과했다.

소스 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

#include <iostream> #define FOR(i,a,b) for(int i = a; i < b; i++) #define endl '\n' #define ll long long using namespace std; ll N, P, Q; ll D[1000000]; ll solve(ll n) {     ll x = n / P, y = n / Q;     if (n == 1) return 2;     else if (n == 0) return 1;     if (n < 1000000) {         if (D[n] != 0) return D[n];         return D[n] = solve(x) + solve(y);     }     return solve(x) + solve(y); } int main() {     D[0] = 1, D[1] = 2;     cin >> N >> P >> Q;     cout << solve(N); } Colored by Color Scripter

cs