[백준] 9095번: 1, 2, 3 더하기 문제 풀이 파이썬
문제 링크
https://www.acmicpc.net/problem/9095
풀이 방식
- 정수 4의 경우의 수는 7(1+2+4)이고, 5의 경우의 수는 13(2+4+7)인걸 확인 가능하다.
- 따라서 정수 N의 경우의 수는 (N-3) + (N-2) + (N-1)의 합으로, 다음과 같은 점화식을 세울 수 있다.
점화식
dp[n] = dp[n-3] + dp[n-2] + dp[n-1]
or
dp[n] = sum(dp[i-3:i])
전체 코드
T = int(input())
for _ in range(T):
N = int(input())
dp = [1, 2, 4]
for i in range(3, N):
dp.append(sum(dp[i-3:i]))
print(dp[N-1])Author And Source
이 문제에 관하여([백준] 9095번: 1, 2, 3 더하기 문제 풀이 파이썬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hyuntall/백준-9095번-1-2-3-더하기-문제-풀이-파이썬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
