https://www.acmicpc.net/problem/1351
1351번: 무한 수열
첫째 줄에 3개의 정수 N, P, Q가 주어진다.
www.acmicpc.net
해당 문제는 dp와 hash를 적용하여 문제를 해결하였다,
처음에, dp만을 활용하여 재귀함수 호출을 통해서 문제를 제출했으나, 시간 초과가 발생하였다. 아무래도 n <= 10^ 12, p, q <= 10^9이다보니, memorization을 활용하지 않아서 그런 것 같다.
* 해당 문제는 Top-down 방식으로 dp를 해결하다보니 memorization이 필요하다.
따라서 map STL 라이브러리를 사용하여 해결하는데, 해당 문제에서 dp의 순서는 크게 상관없기때문에 상대적으로 더 간단한 unordered_map을 활용한다. 또한 배열로 선언하기에는 n이 너무 크므로, map을 활용하여 필요한 값들만 따로 저장해두므로 훨씬 편리하다.
또한,
A[0] = 1
A[i] = A[i/p] + A[j/q] 이므로 다음과 같이 코드를 작성하였다.
#include <iostream>
#include <unordered_map>
using namespace std;
long long n, p, q;
long long res = 0;
unordered_map<long long, long long> m;
long long solution(long long x)
{
if (x == 0)
return 1;
if (m[x] != 0)
{
return m[x];
}
else
{
return m[x] = solution(x / p) + solution(x / q);
}
}
int main(int argc, char const *argv[])
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> p >> q;
m[0] = 1;
cout << solution(n);
return 0;
}
'알고리즘' 카테고리의 다른 글
백준[17298번] 오큰수 C++ (0) | 2023.11.07 |
---|---|
백준[2230번] 수 고르기 C++ (0) | 2023.11.06 |
백준[15663번] N과 M(9) (2) | 2023.10.31 |
백준[2133번] 타일 채우기 (0) | 2023.10.30 |
백준[3197번] 백조와 호수 (0) | 2023.09.19 |