개요

백준 1351번: 무한 수열

• 입력
  첫째 줄에 3개의 정수 N, P, Q가 주어진다.

• 출력
  첫째 줄에 AN을 출력한다.

접근 방식

1. 기본적인 dp형식의 문제라 dp처럼 배열 생성하고 풀려했으나,
   N의 크기가 최대 10의 12승이라 그만한 배열을 만들면 메모리가 초과된다.
2. 따라서 방법을 검색해본 결과 map을 사용해야한다. 어차피
   최소 P,Q는 2니까 log를 씌워보면 40개 정도도 안들어간다.
3. 주의사항은 값들도 최대값이 10의 12승이므로 int형쓰면 안되고 long long int형을
   사용해야한다.

전체 코드

#include<iostream>
#include<map>
#include<math.h>
using namespace std;
long long int N;
int P, Q;
//일반 배열로 dp처럼 풀기엔 10^12* 8 바이트 크기를 못 감당함 
//하지만 map을 사용해 값을 넣어주는 식으로하면 실제 저장할 값이 몇 안되어서 풀기 가능하다
map<long long, long long> dp;
void Input() {
	cin >> N >> P >> Q;
	dp[0] = 1;
}

long long returnValueA(long long n) {
	if (dp[n]) return dp[n];	
	long long devidedByP = returnValueA(n / P);
	long long devidedByN = returnValueA(n / Q);
	dp[n] = devidedByP + devidedByN;
	return dp[n];
}

int main() {	
	ios_base::sync_with_stdio(0);
	Input();
	cout << returnValueA(N);
}

문풀후생

dp에서 갯수가 작다면 꼭 배열을 안쓰고 map쓰는게 효율적이라는 걸 배운 문제였다.