https://www.acmicpc.net/problem/1354
- Ai = 1 (i ≤ 0)
- Ai = A⌊i / P⌋ - X + A⌊i / Q⌋ - Y (i ≥ 1)
여기에서 An을 구하는 문제입니다.
우선 N이 10^13이기 때문에 단순 배열만으로는 해결할 수 없습니다.
그래서 처음 생각해낸건 map을 사용하여 dp를 해결하려고 했습니다.
dp 재귀를 돌릴 때 dp[n] != -1이면 dp[n]을 리턴했던것 처럼
map에 포함되어 있는 수는 이미 방문처리가 되었으므로 그 수를 리턴하도록 합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long ll;
unordered_map<ll, ll> m;
ll N, p, q, x, y;
ll solve(ll n) {
if (n <= 0) return 1LL;
if (m.find(n) != m.end()) return m[n];
return m[n] = solve(n / p - x) + solve(n / q - y);
}
void func() {
cout << solve(N) << '\n';
}
void input() {
cin >> N >> p >> q >> x >> y;
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
근데 생각보다 메모리를 많이 차지하고, 시간도 많이 소요되는 것을 알 수 있습니다.
다른분들의 제출 현황을 보니 이 방법은 비효율적이라는 것을 알 수 있었습니다.
제가 확인해봤던 풀이로는 배열을 활용하는 방법이었습니다.
하지만 N의 범위가 10^13이기 때문에 모든 범위를 배열로 해결할 수는 없습니다.
문제에서 허용하는 메모리 512MB 내에서는 가능하기 때문에 10000000 까지는 배열로, 나머지는 재귀로 해결할 수 있었습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <iostream>
#include <algorithm>
#define MAX 10000001
using namespace std;
typedef long long ll;
ll dp[MAX];
ll N, p, q, x, y;
ll solve(ll n) {
if (n < MAX) return dp[n];
ll l = 1LL;
if (n / p - x > 0) l = solve(n / p - x);
ll r = 1LL;
if (n / q - y > 0) r = solve(n / q - y);
return l + r;
}
void init() {
dp[0] = 1LL;
for (int i = 1; i < MAX; i++) {
dp[i] = dp[max(0LL, i / p - x)] + dp[max(0LL, i / q - y)];
}
}
void func() {
init();
cout << solve(N) << '\n';
}
void input() {
cin >> N >> p >> q >> x >> y;
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
아까와 비교하면 메모리와 시간 차이가 정말 많이 난다는 것을 알 수 있습니다.
'algorithm > dp' 카테고리의 다른 글
| boj 25378 조약돌 (0) | 2024.06.29 |
|---|---|
| boj 2216 문자열과 점수 (0) | 2024.06.28 |
| boj 3114 사과와 바나나 (0) | 2024.06.13 |
| boj 11560 다항식 게임 (0) | 2024.06.13 |
| boj 28018 시간이 겹칠까? (0) | 2023.08.08 |