반응형
https://www.acmicpc.net/problem/1354
1354번: 무한 수열 2
첫째 줄에 5개의 정수 N, P, Q, X, Y가 주어진다.
www.acmicpc.net
[ 문제풀이 ]
1. unordered_map< ll, ll> um을 선언합니다.
2. 재귀함수를 통해 n이 0보다 작거나 같으면 1을 return하고, um.count(n)이 0일 때 um[ n ] = dfs(n / P) + dfs(n / Q)를 통해 um[ n ]을 구해줍니다.
3. dfs(N)을 출력합니다.
[ 소스코드 ]
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 | #include<iostream> #include<unordered_map> #define ll long long using namespace std; ll N; int P, Q, X, Y; unordered_map<ll, ll> um; ll dfs(ll n) { if (n <= 0) return um[n] = 1; if (um.count(n) != 0) return um[n]; return um[n] = dfs(n / P - X) + dfs(n / Q - Y); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> P >> Q >> X >> Y; cout << dfs(N); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 2661번 - 좋은수열 (C++) (1) | 2023.10.04 |
|---|---|
| [ 백준 ] 1461번 - 도서관 (C++) (0) | 2023.10.03 |
| [ 백준 ] 2174번 - 로봇 시뮬레이션 (C++) (0) | 2023.10.01 |
| [ 백준 ] 14719번 - 빗물 (C++) (0) | 2023.09.30 |
| [ 백준 ] 9177번 - 단어 섞기 (C++) (0) | 2023.09.29 |