백준 9095 문제 풀이 python
🐒 1, 2, 3 더하기
https://www.acmicpc.net/problem/9095
✍ 나의 풀이
import sys
dp = [0] * 11
dp[1] = 1
dp[2] = 2
dp[3] = 4
for i in range(4,11):
dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
t = int(input())
for _ in range(t):
n = int(sys.stdin.readline().rstrip())
print(dp[n])
어떻게 풀어야할지 몰라서 다른 사람들의 풀이를 봤는데, 세번쩌 전 항과 두번째 전항과 이전항의 합이 현재항의 값이 되는 규칙이 있었다. 마치 피보나치 수열처럼
🧠 문제 이해
n이 최대 10 밖에 안되므로
미리 1부터 10까지 경우의 수를 계산해 놓고
입력되는 정수에 따라서 경우의 수를 출력해준다.
DP 테이블
dp = [0] * 11
# 1부터 n까지 1,2,3의 합으로 나타낼 수 있는 경우의 수를 저장할 리스트를 만든다.
# n은 양수이며 11보다 작다
dp[1] = 1
dp[2] = 2
dp[3] = 4
for i in range(4,11):
dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
# 반복문으로 이전항을 이용해 1부터 10까지의 경우의 수를 저장한다.
DP테이블에 모든 경우의 수를 담았으니
입력되는 값에 따라 출력만 해주면 된다.
t = int(input())
for _ in range(t):
n = int(sys.stdin.readline().rstrip())
# 반복문에서 받는 입력은 readline()이 처리가 빠르다
print(dp[n])
Author And Source
이 문제에 관하여(백준 9095 문제 풀이 python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mauserne/백준-9095-문제-풀이-python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)