728x90
https://www.acmicpc.net/problem/1351
1351번: 무한 수열
첫째 줄에 3개의 정수 N, P, Q가 주어진다.
www.acmicpc.net
A0는 1로 주어지고, Ai ~ An은 주어지지 않았다.
대신 점화식으로 Ai = Ai/p + Ai/q인데, p와 q 값이 난수이다.
그러므로 확정적으로 아는 값은 A0뿐이고, p와 q에 따라 Ai의 값이 변한다.
먼저 예제 1번을 가지고 규칙을 찾아보았다.
N = 7, P = 2, Q = 3의 입력이 주어졌을 때, Ai는 아래와 같다.
A0 = 1
A1 = A0 + A0 = 2
A2 = A1 + A0 = 3
A3 = A1 + A1 = 4
A4 = A2 + A1 = 5
A5 = A2 + A1 = 5
A6 = A3 + A2 = 7
A7 = A3 + A2 = 7
여기서 P로 나누어지는 수는 Ai/p로, i를 p로 나눈 몫이었고, Q로 나누어지는 수는 Ai/q로 역시 i를 q로 나눈 몫이었다.
그래서 생각한 접근은 재귀적으로 문제를 해결하는 것이었다.
쉽게 말해,
A7 = A3 + A2인데,
A3은 다시 A1 + A1으로 구할수 있고, A2는 A1 + A0으로 구할 수 있다.
다시 A1은 A0 + A0로 구해지므로 i값이 0이 아닌 경우 계속해서 p와 q로 나눈 수를 더해주면 된다.
그래서 세운 재귀식
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include <iostream>
using namespace std;
using ll=long long;
ll div(ll x, ll p, ll q){
if(x==0) return 1;
else return div(x/p, p, q)+div(x/q, p, q);
}
int main(){
ll n, p, q, ans=0; cin >> n >> p >> q;
if(!n){
cout << 1;
return 0;
}
ans=div(n/p, p, q)+div(n/q, p, q);
cout << ans;
}
|
cs |
그런데 위 코드에서는 TLE가 발생했다.
그래서 dp로 접근하려고보니 범위가 10^12이었으므로, 배열이 아닌 map을 이용하여 수를 저장하도록 설계했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include <iostream>
#include <map>
using namespace std;
using ll=long long;
map<ll, ll>dp;
ll div(ll x, ll p, ll q) {
if(dp[x]) return dp[x];
else return dp[x]=div(x/p, p, q)+div(x/q, p, q);
}
int main(){
ll n, p, q, ans=0; cin >> n >> p >> q;
dp[0]=1;
ans=div(n/p, p, q)+div(n/q, p, q);
if(!n) ans=1;
cout << ans;
}
|
cs |
'PS > BOJ' 카테고리의 다른 글
[C++] 백준 20166번: 홀수 홀릭 호석 - Recursion (0) | 2024.01.12 |
---|---|
[C++] 백준 7570번: 줄 세우기 - DP (0) | 2024.01.09 |
[C++] 백준 23084번: IUPC와 비밀번호 - Sliding Window (0) | 2023.09.17 |