https://www.acmicpc.net/problem/1351
1351번: 무한 수열
첫째 줄에 3개의 정수 N, P, Q가 주어진다.
www.acmicpc.net
N의 최댓값이 10^12 이므로 배열이나 벡터는 사용할 수 없다.
중복되는 값들을 쉽게 해결하기 위해 memoization을 활용한다. 이때 이전의 값들을 알기는 해야 하지만 1~최댓값 사이의 모든 수를 사용하지는 않을 것이기 때문에 unordered_map을 사용하여 key : value 형태로 저장하여 중복되는 값들을 활용하도록 한다.
문제를 보고서는 배열을 사용할 수 없지만 재귀함수를 이용하면 풀 수 있을 것 같았다. N의 최대값을 크지만 PQ가 2만 되도 logN이 되므로 많은 양의 배열이 필요 할 것 같지는 않아 key : value 형태로 사용할 수 있도록 unordered_map을 활용하였다. 이 문제를 풀면서 map 과 unordered_map에 대해 한번 더 알아보게 되었다. 그래서 두 자료구조의 차이를 보기 위해 두개 다 제출해보았지만 둘다 0ms가 걸려 이문제로는 차이를 느낄 수가 없었다!
'코딩 > 백준' 카테고리의 다른 글
| [백준]17135번 캐슬 디펜스 - C++ (0) | 2023.02.08 |
|---|---|
| [백준] 1563번 - 개근상 (0) | 2023.02.06 |
| [백준]1744번 수 묶기 - C++ (0) | 2023.02.03 |
| [백준]17142 연구소3 - C++ (0) | 2023.01.31 |
| [백준]2251번 물통 - C++ (0) | 2023.01.30 |