이번 문제는 백준의 골드 5 문제 무한 수열문제이다.
문제를 차근차근 한 번 읽어보자.
어떤 수열의 값 An을 구하고 싶다.
이 때, Ai = A(i/p) + A(i/q)이며, p와 q는 값이 주어진다.
N의 최대 값은 10^12이며, p와 q는 10^9이다.
굉장히 큰 값이기 때문에 시간 초과가 문제가 될 것 같다.
문제를 어떻게 풀어나가야 할까?
재귀
가장 먼저 든 생각은 재귀로 파고드는 것이다.
우선 당연히 매우 큰 수 이기 때문에 long long 자료형을 사용한다.
우리가 원하는 것은 An이기 때문에, n/p, n/q로 파고들면 될 것같다.
그럼 수는 어디에 저장해야 할까?
배열에 저장하면서 나아간다면 어떨까?
N의 최대 값이 10^12이기 때문에 그건 불가능 할 것 같다.
n번째 수열의 값을 곧바로 저장할 수 있는 자료구조는 없을까?
바로 unordered_map이 있다.
이는 Hash table과 동일한 자료구조로, 키를 통해 값을 불러올 수 있다.
즉, Ai에 대해 hash_table[i]에 저장을 하여 값을 계산할 것이다.
A0 = 1이라는 기저조건이 있으므로, 0이 되면 1을 반환하면 될 것 같다.
0까지 쭉 재귀적으로 파고든 뒤, 위로 올라오며 값을 계산하도록 해보자.
unordered_map<ll, ll> hash_table;
ll calculate_sequence(ll target) {
if (target == 0)
return 1;
hash_table[target] = calculate_sequence(target / p) + calculate_sequence(target / q);
return hash_table[target];
}
int main() {
cin >> n >> p >> q;
calculate_sequence(n);
cout << hash_table[n];
return 0;
}위와 같이 구현해보았는데, 유감스럽게도 시간 초과가 발생했다.
어떤 부분이 문제였을까?
원인은 중지 조건
결국 원인을 찾지 못하고 다른 사람들의 풀이를 참고했다.
원인은 내 코드의 중지 조건에 있었다.
내가 짰던 코드는 0을 만나면 1을 반환하도록 하고 있다.
그 말은, 0이 나올 때 까지는 계속 재귀를 반복하겠다는 의미이다.
하지만 굳이 그럴 필요가 있을까?
0이 아니라, key:value 관계에서 value가 0이 아닐 때 중지한다면?
target을 계속 나누다가, 이미 계산된 target을 만나면 중지하는 것이다.
그렇다면 굳이 0까지 다시 내려갔다 올라와야 하는 시간을 줄일 수 있다.
unordered_map<ll, ll> hash_table;
ll calculate_sequence(ll target) {
if (hash_table[target] != 0)
return hash_table[target];
hash_table[target] = calculate_sequence(target / p) + calculate_sequence(target / q);
return hash_table[target];
}
int main() {
cin >> n >> p >> q;
hash_table[0] = 1; // 기저 조건
cout << calculate_sequence(n);
return 0;
}참조자(&)
C++의 특이한 연산자인 &를 이용한 풀이도 있었다.
&를 붙이면 시간초과가 발생하지 않고, 없으면 시간초과가 난다.
굉장히 신기한 광경이다.
unordered_map<ll, ll> hash_table;
ll calculate_sequence(ll target) {
if (target == 0)
return 1;
ll& ret = hash_table[target];
if (ret != 0)
return ret;
return ret = calculate_sequence(target / p) + calculate_sequence(target / q);
}