반응형 Infinity Series1 #1351 무한 수열 (Dynamic Programming) 이번 문제는 Gold IV 난이도로 설정되어 있습니다. 무한히 이어지는 수열이 있는데, 이 수열은 다음과 같은 규칙을 가지고 있습니다. 주어진 자연수 P, Q에 대하여 \(A_i\) 항은, \[ A_i = A_{ \lfloor i/P \rfloor } + A_{\lfloor i/Q \rfloor } \] 계속 나누어주는 것이기 때문에 \(A_0\)까지 가는데 빠릅니다. 많아야 \( \log_{P} N + \log_{Q} N \) 번이니까요. 동적 프로그래밍을 이용해서 풀어놓기는 했지만, 그냥 풀어도 적절한 시간안에 풀 수 있는 문제일거라고 보입니다. N의 숫자가 크기 때문에 저는 map 자료구조를 이용해서 풀었습니다. 풀어놓고 보면, 정말 쉬운 문제입니다. 소스도 크게 어려울 것이 없습니다. 제가 작성한.. 2020. 2. 1. 이전 1 다음 728x90