[백준] 1351번
💻 C++ 기반
✔️ bottom-up DP를 이용하면 N이 너무 커서 안됨
✔️ top-down 방식을 사용할건데 그냥 재귀를 사용하면 시간초과가 남 -> 값을 저장해주는 메모이제이션 필요
#include <cstdio>
#include <unordered_map>
using namespace std;
long long N, P, Q;
unordered_map<long long, long long> m;
long long dp(long long num)
{
if (m.find(num) != m.end())
{
return m[num];
}
else
{
return m[num] = dp(num/P) + dp(num/Q);
}
}
int main()
{
scanf("%lld %lld %lld", &N, &P, &Q);
m[0] = 1;
printf("%lld", dp(N));
return 0;
}
Author And Source
이 문제에 관하여([백준] 1351번), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jieun_han/백준-1351번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)