BOJ 1351 - 무한 수열

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

1351번: 무한 수열

개인적으로 매우 신박한 문제다.

대놓고 기본 dp문제인데 dp배열로 풀기엔 배열 크기가 오버된다.

 

map을 사용해서 dp하는 문제다.

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

map<long long, long long> dp;
long long n, p, q;

long long f(long long n) {
	if (n == 0)return 1;
	auto ret = dp.find(n);
	if (ret != dp.end()) return ret->second;
	
	long long rst = 0;
	rst = f(n / p) + f(n / q);
	dp.insert({ n, rst });
	return rst;
}

int main() {
	cin >> n >> p >> q;
	cout << f(n) << '\n';
}

map.first가 key(index)이고 map.second는 value이다.