[G5] 백준 1351번 무한 수열 C++ 다이나믹 프로그래밍, 해시맵, 재귀

리뷰

 

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

재귀를 통해 n을 p와 q의 관점에서 최적해를 구하고, 이미 구한 값을 기억해두어 재귀 탐색을 최소화 하는 문제

 

 

전역 변수

• n : 답을 구하고자 하는 인덱스를 저장할 변수
• p, q : 인덱스에 나누어 몫을 구하기 위한 값을 저장할 변수
• dp : 메모제이션을 활용하기 위한 해시맵

 

함수

1. solve

ll solve(ll num)

 

재귀를 통해 최적해를 찾기 위한 함수

1. 매개변수로 탐색을 진행할 인덱스 num을 입력 받는다.
2. 기저 조건으로 이미 dp의 num 인덱스가 구해진 상태라면 해당 값을 리턴해 준다.
3. 기저 조건에 해당하지 않는다면 num을 p와 q로 나눈 값을 매개변수로 전달하여 재귀를 진행한다.
4. 재귀를 빠져나오며 dp의 num 인덱스에 3번에서 구한 값을 더해 저장해 준다.
5. 해당 값을 리턴해 현재 재귀를 빠져나와준다.

 

문제풀이

1. n, p, q를 입력 받고, dp의 0번 인덱스를 1로 저장해 준다.
2. 만약 n이 0이라면 1을, 아니라면 solve에 n / p, n / q를 매개변수로 전달하여 리턴받은 값을 더해 출력한다.

 

트러블 슈팅

1. p, q와 solve 함수의 매개변수 num을 int로 설정했다가 60%에서 틀렸습니다를 받았다.
2. p, q는 상관 없을 것 같은데 n과 num은 long long타입으로 설정해야 할 것 같다. 물론 해시맵의 key도 포함

 

참고 사항

• 0번 값은 재귀호출하기 전에 1로 명시해 주어야 한다, 그렇지 않으면 값을 구할 수 없다.

 

정답 코드

#include<iostream>
#include<unordered_map>
#define ll long long
using namespace std;

ll n, p, q;
unordered_map<ll, ll> dp;

ll solve(ll num) {
	if (dp[num]) return dp[num];
	dp[num] = solve(num / p) + solve(num / q);
	return dp[num];
}

int main() {
	cin >> n >> p >> q;
	dp[0] = 1;
	
	if (!n) cout << 1;
	else cout << solve(n / p) + solve(n / q);
}