백준 1351 무한 수열

www.acmicpc.net/problem/1351

1351번: 무한 수열

이 문제는 dp유형이다. dp 배열을 map으로 만들어주어서 문제를 해결할 수 있었다. 

 

왜 map을 사용했을까? 우선 입력값을 보면 10^12로 매우 크다 이를 배열로 표현하기에는 크게 무리가 있다고 생각했다. 그래서 나는 이 숫자들을 문자열로 만들어서 map의 키 값으로 지정하여 value를 저장하는 캐시를 만들어 주어 쉽게 해결할 수 있었다. 그 나머지는 조건 그대로 재귀를 구성해주면 된다. 

 

#include <cstdio>
#include <map>
#include <string>
using namespace std;

#define ll long long

map<string, ll> mp;

ll getNum(ll num);
ll N, P, Q;

int main(){
	scanf("%lld %lld %lld", &N, &P, &Q);
	printf("%lld", getNum(N));
}


ll getNum(ll num){
	if(num == 0)
		return 1;

	if(mp.find(to_string(num)) != mp.end()){
		return mp[to_string(num)];
	}

	return mp[to_string(num)] = getNum(num/P) + getNum(num/Q);
}