[백준] C++ 1354번 무한 수열2

이 문제는 HashMap과 재귀함수를 활용해서 해결하는 문제이다.

 

문제해결방법

1.HashMap에 만약 내가 필요한 값이 있다면 바로 return을 하고 없다면 재귀적으로 그 값을 찾는 함수를 작성해야한다.

(hashMap[0]=1)

 

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

long long N, P, Q, X, Y = 0;
unordered_map<long long, long long> hashMap;
long long sol(long long num);

int main(void)
{
	cin >> N >> P >> Q >> X >> Y;

	hashMap[0] = 1;
	cout << sol(N);
	return 0;
}
long long  sol(long long num)
{
	if (hashMap.find(num) != hashMap.end())//해쉬 맵에 필요한 값이 존재하는가??
	{
		return hashMap[num];
	}
	else//값이 존재하지 않는다면 값을 찾자
	{
		long long temp1, temp2 = 0;
		if ((num / P - X) <= 0)
		{
			temp1 = 1;
		}
		else
		{
			temp1 = sol(num / P - X);
		}
		
		if ((num / Q - Y) <= 0)
		{
			temp2 = 1;
		}
		else
		{
			temp2 = sol(num / Q - Y);
		}
			
		hashMap[num] = temp1 + temp2;

		return hashMap[num];
	}
}