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

A(i)=A(i/P)+A(i/Q)을 이용해서 A(N)을 구하는 문제이다.

N의 범위가 10^12까지여서 일반적인 배열을 이용해서는 문제를 해결할 수 없다.

재귀함수를 통해 계속해서 밑으로 내려간 후 밑에서부터 결과값을 가지고 차근차근 올라오는 느낌으로 문제를 해결해야 한다. 그렇다면 A [temp]의 값은 어디에 저장을 하는가?? HashMap에 저장을 하면 된다. hashMap [temp]=A [temp]이런 식으로 저장하면 된다. (unordered_map <int, int>)

 

문제해결방법

1. hashMap에 찾고자 하는 값이 있다면 바로 return을 하고 찾고자하는 값이 없다면 재귀적으로 계속 값을 찾아나간다.

2. 만약 N=1으로 입력이 들어오면 1을 출력해야 함에 주의하자.

3. int형이 아닌 long long으로 선언해야 한다.

 

#include <iostream>
#include <unordered_map>

using namespace std;

long long sol(long long num);

unordered_map<long long, long long> hashMap;
long long N, P, Q = 0;
int main(void)
{
	cin >> N >> P >> Q;
	hashMap[0] = 1;
	if (N == 0)
	{
		cout << 1;
	}
	else
	{
		cout << sol(N / P) + sol(N / Q);
	}
	
	return 0;
}

long long sol(long long num)
{
	long long result = 0;
	if (hashMap.find(num) != hashMap.end())//hashMap에 찾고자하는 값이 있다면 return한다.
	{
		return hashMap[num];
	}
	result = sol(num / P) + sol(num/Q);//찾고자하는 값이 없다면 값을 구한다.
	hashMap[num] = result;
	return result;
}