[백준/C++] 1351 무한 수열

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

 

코드

#include <iostream>
#include <unordered_map>
using namespace std;

#define FASTIO ios::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;

unordered_map<int, ll> m; 
ll n, p, q;

ll solve(ll now) {
	if (m[now] != 0) return m[now];
	m[now] = solve(now / p) + solve(now / q);
	return m[now];
}

int main() {
	FASTIO;
	cin >> n >> p >> q;
	m[0] = 1;
	cout << solve(n) ;
	return 0;
}

설명

재귀함수를 문제에서 제시된 식 형태로 계속 호출해나가며 답을 구해나간다. 

느낀 점

구현 자체는 어렵지 않았다. 처음에는 bottom-up으로 풀었더니 메모리 초과가 났다. 그래서 top-down으로 바꿔서 다시 제출하니 바로 통과했다. 저번에 map을 이용해서 시간초과가 났던 문제가 unordered_map을 쓰니 바로 통과한 경우가 있어서 처음부터 unordered_map을 사용했다!