목록2025/02/21 (1)

AtraFelis's Develop Diary

[99클럽 코테스터디 25일차 TIL / 백준] 1351 - 무한 수열 (DP, HashMap)

99클럽 코테스터디 25일차 TILKeyWord : DP, Map문제무한 수열 A는 다음과 같다.$A_0 = 1$$A_i = A_{⌊i/P⌋} + A_{⌊i/Q⌋} (i ≥ 1)$N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.입력첫째 줄에 3개의 정수 N, P, Q가 주어진다.출력첫째 줄에 AN을 출력한다.제한$0 ≤ N ≤ 10^{12}$$2 ≤ P, Q ≤ 10^9$  풀이매우 간단한 DP 문제이다. 처음부터 문제에 수열의 점화식도 주어졌으므로, 그대로 메모제이션을 하면서 코드를 구현하면 될 듯하다. (bottom-up 방식이 아닌, top-down의 재귀 방식으로 구현하면 쉽다.)하지만 이 정도만 고려하고 곧장 코드를 구현한다면 반드시 실패할 것인데, 아래의 조건 때문이다.$0 ≤..
Algorithm/백준 2025. 2. 21. 17:00
이전 Prev 1 Next 다음