백준 1351 풀이

목표: 백준 1351 풀기

환경: mac OS Mojave 10.14, CLion

로직

문제이해

점화식이 주어진 DP 문제

문제접근

DP의 두 가지 핵심 개념
overlapping subproblem : 작은 문제가 겹친다. ( 작은 문제가 여러 번 발생한다.) optimal substructure : (어떻게 풀든 작은 문제의 답은 항상 같다. 그러니 가져다 쓸 수 있다.)

이 두가지 개념을 가능하게 해주는 memoization 그냥 한번 풀이한 작은 문제는 또 풀이하지 않고, 가져다 쓰기.

여기에 + 2가지.

  1. 오개념 있었다. 정확히 말하면 그동안 코딩은 대충했다는 것
    0을 0이 아닌 양의 정수로 나누는 연산이 에러인 줄 알았음. n을 0으로 나누었을때 에러가 남.

  2. 보통 메모이제이션을 배열로 사용한다. 그러나 이 문제는 범위가 int 데이터 사이즈를 벗어난다.
    long long 으로 인덱스를 주고싶다. 전에 string을 인덱스로 주고 싶을때는?
    map을 사용했었다. 똑같다. int형이 아닌 값을 인덱스로 사용하고싶으면? map을 쓰자.

#include <iostream>
#include <map>

using namespace std;
long long n, p, q;
map<long long, long long> cache;
long long solve(long long n){
    if(cache.count(n)){
        return cache[n];
    }else{
        return cache[n] = solve(n/p) + solve(n/q);
    }
}

int main() {

    cache[0] = 1;

    cin >> n >> p >> q;

    cout<<solve(n)<<'\n';

    return 0;
}