역시나 처음에 조합부터 떠오른 1인.. 하지만 시간 초과 뜰 게 뻔해서 dp로 다시 방향을 바꾸었다! 이 문제는 피보나치 수열과 매우 유사하다. n=1일때 1개 n=2일때 2개 n=3일때 3개 (1+2) n=4일때 5개 (2+3) dp[n]=dp[n-1]+dp[n-2] 그래서 간단하게 답을 도출해낼 수 있었다. 정답코드는 아래와 같다 n=int(input()) dp=[0] * 1000001 dp[1]=1 dp[2]=2 for i in range(3,n+1): dp[i]=(dp[i-1]+dp[i-2])%15746 print(dp[n]) 위 코드 같은 경우에는 시간이 473ms가 떠서 더 좋은 방식이 있나 찾아봤더니 행렬곱셈을 이용하여 피보나치 수열을 하게 되면 더 빠르게 값이 도출된다는 것을 알게 되었다...
