[백준/Python(파이썬)] 9095 1, 2, 3 더하기

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

풀이

 쉬운 동적계획법 문제

소스코드

n = int(input())
dp = [1, 2, 4]  # n이 1, 2, 3일 때 방법의 수
for i in range(3, 11):
    dp.append(dp[i-1]+dp[i-2]+dp[i-3])
    # 동적계획법 : 미리 배열에 저장해둔(구해둔) 값을 이용해 처리하는 것 => 규칙찾기
for j in range(n):
    m = int(input())
    print(dp[m-1]).

Git : github.com/jisun1125/algorithm-problem-solving/blob/main/baekjoon/no_9095.py

문제 : https://www.acmicpc.net/problem/9095