파도반 수열1 [Kotlin] 백준 27435 : 파도반 수열 2 문제 링크 27435번: 파도반 수열 2 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ T ≤ 1,000, 1 ≤ N ≤ 1018) www.acmicpc.net 문제 해설 [Kotlin] 백준 9461 : 파도반 수열의 확장 버전 문제이다. 이전 문제는 입력값이 최대 100이었기 때문에 DP로 충분히 해결할 수 있는 문제였지만, 이 문제는 입력값이 최대 1018이나 되기 때문에 DP로 풀게 되면 시간초과가 발생한다. 따라서 파도반 수열의 성질을 이용하여 풀어야 한다. 파도반 수열에 대해 다음과 같이 피보나치 Q-행렬과 유사한 행렬(이하 Q-행렬)이 존재한다. $$Q=\begin{bmatrix}0&1&0\\0&0&1\\1&1&0\\\e.. 2023. 4. 27. 이전 1 다음
