백준 1351: 무한 수열

문제 요약

무한 수열 A는 다음과 같다.

• $A_0 = 1$
• $A_i = A_{⌊i/P⌋} + A_{⌊i/Q⌋} (i ≥ 1)$
  
  N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.

문제 분류

• 다이나믹 프로그래밍
• 자료 구조
• 해시를 사용한 집합과 맵

문제 풀이

한 쌍으로 주어지는 간선을 표현하는 방법에 대해, pair객체를 vector의 원소로 두는 방법, 그리고 multimap을 사용하는 방법이 있다.

vector와 multimap의 시간복잡도를 비교해보면 vector의 정렬에 O(nlogn)만큼 걸리고, 원소 탐색에 O(n)이라고 생각할 수 있다.

mulitmap을 이용할 경우 삽입과 동시에 정렬되므로 삽입에 O(logn), 탐색에 O(logn)정도로 multimap이 훨씬 효율적인 방법이라고 할 수 있겠다.

이전에 vector로 풀었던 적이 있어서, multimap 으로 다시 풀어보았다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

int p, q;
map<long long, long long> m;

long long sol(long long n) {
	if (n == 0) return 1;
	if (m.find(n) != m.end()) return m[n];
	long long res = sol(n / p) + sol(n / q);
	m.insert({ n, res });
	return res;
}

int main()
{
	long long n;
	scanf("%lld%d%d", &n, &p, &q);

	printf("%lld", sol(n));
	
	return 0;
}