[#9095] 1, 2, 3 더하기

문제

#9095 1, 2, 3 더하기
Silver4
적용 알고리즘: 동적 계획법 알고리즘

---

풀이 방법

• 1, 2, 3, 4부터 시작하여 낮은 수일 때의 값을 구해 규칙의 패턴을 분석한다.
• 1일때는 1, 2일 때는 2, 3일 때는 4, 4일 때는 7의 값을 가진다.
• 현재의 수는 현재 이전의 연달아 오는 세 개의 수의 합이다.
• 출력을 원하는 값은 여러 개를 요구하는데, n의 값도 작고 하여 dp배열을 다 구해 놓고 사용자가 입력한 값을 배열에서 찾아서 출력하면 된다.

코드 흐름

1. dp 배열을 생성한다. 1, 2, 3부터 초기 값은 각각 1, 2, 4이다.
2. 반복문을 4부터 10까지 돌며(문제의 범위이다), dp 배열의 값을 채워나간다. dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] 이다.
3. 사용자의 입력을 받고, 해당하는 위치에 있는 dp배열의 값을 출력한다.

코드

dp = [0] * 11
dp[1] = 1
dp[2] = 2
dp[3] = 4

for i in range(4, 11):
    dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
    
t = int(input())
for i in range(t):
    print(dp[int(input())])

체감 난이도: 3/5
규칙만 알아내면 코딩하기에는 쉬운 문제였다.