[Baekjoon] 9095번 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

 

=> 기존 백준 문제를 Javascript를 이용해 풀이하였었는데, 입출력관련해서 맞게 풀어도 틀리다 나오는 경우가 있어서 백준의 경우는 python을 사용해서 풀이하기로 결정하였다. 

 

▶ 코드 : 

# https://www.acmicpc.net/problem/9095
# 백준 1, 2, 3 더하기

T = int(input())
testCase = []

for t in range(T):
    testCase.append(int(input()))

maxNum = max(testCase)
dp = [0 for _ in range(maxNum+1)]

dp[1] = 1
dp[2] = 2
dp[3] = 4

for i in range(4, maxNum+1):
    dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

for t in testCase:
    print(dp[t])

 

 

▶ 문제풀이 : 

- DP 문제이다. 

1. 초기 입력을 받아 입력 중 가장 큰수를 찾는다. 

2. 그후 maxNum만큼 반복문을 돌며 dp 배열에 값을 저장한다. 

 

=> 해당 문제에서는 1, 2, 3으로 덧셈을 표현하는 모든 경우의 수를 출력하는 문제이다. 

=> 이때 각 수 별로 시작하는 값이 1, 2, 3 일때 나올 수 있는 모든 경우의 수를 찾기 위한 점화식은 

 

F(n) = F(n-1) + F(n-2) + F(n-3) 

이다. 

따라서 위의 점화식을 이용해 for문을 돌려주면 dp 배열을 누적했고, 이때 주어진 입력에서 가장 큰 수만큼 반복하며 배열을 채운다음 결과를 출력해준다.