반응형
https://www.acmicpc.net/problem/1351
1351번: 무한 수열
첫째 줄에 3개의 정수 N, P, Q가 주어진다.
www.acmicpc.net
[ 문제풀이 ]
1. unordered_map< ll, ll> um을 선언하고, um[ 0 ] = 1로 초기화합니다.
2. 재귀함수를 통해 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 29 | #include<iostream> #include<unordered_map> #define ll long long using namespace std; ll N; int P, Q; unordered_map<ll, ll> um; ll dfs(ll n) { if (um.count(n)) return um[n]; return um[n] = dfs(n / P) + dfs(n / Q); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> P >> Q; um[0] = 1; cout << dfs(N); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 14719번 - 빗물 (C++) (0) | 2023.09.30 |
|---|---|
| [ 백준 ] 9177번 - 단어 섞기 (C++) (0) | 2023.09.29 |
| [ 백준 ] 14925번 - 목장 건설하기 (C++) (0) | 2023.09.27 |
| [ 백준 ] 20924번 - 트리의 기둥과 가지 (C++) (0) | 2023.09.26 |
| [ 백준 ] 10835번 - 카드게임 (C++) (0) | 2023.09.25 |