(백준 1351번 무한수열 C++) 라이님 블로그 대회 알고리즘 따라잡기 11) BST

어제 풀다가 삽질한 문제 1351번!

역시 머리가 맑은 아침에는 잘 풀린다^__^

 

백준 1351번 무한수열

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

 

문제를 풀다가 처음에는 메모리 초과 -> 틀렸습니다 이슈로 고생 좀 했는데,

 

1. 메모리 초과가 된 이유 : vector를 사용했기 때문 → map을 사용해야 한다!!

2. 틀렸습니다가 계속 뜬 이유 : long long...^^

 

vector가 아닌 map을 사용해서 문제를 풀어야 하는 이유는 아래 답글을 참고하세요↓

https://www.acmicpc.net/board/view/137948

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

map<long long, long long> m;
long long N, P, Q;

long long dp(long long n) {
	if (n == 0) return 1;
	if (m.find(n)!= m.end()) return m[n];
	long long NP = n / P; 
	long long NQ = n / Q;
	m[n] = dp(NP) + dp(NQ);
	return m[n];
}

int main() {
	cin >> N >> P >> Q;

	cout << dp(N) << endl;
	return 0;
}