1,2,3 더하기 백준 9095번 DP

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

문제 정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

정렬을 끝내고 오늘부터 DP(다이나믹프로그래밍)을 시작합니다. 지난 게시글에서도 몇번 DP문제를 푼적이 있었는데 말머리를 DP로 통일해놓아야 겠습니다.

DP에서 핵심은 점화식을 찾고 이를 코드로 구현하는 것이 전부입니다. 밑도 끝도 어렵게 만들 수도 있지만 보통 코딩테스트에서 요구하는 수준은 거기까지는 안간다고 하네요 저도 22년도 NC공채에서 코테를 볼때 DP문제가 마지막에 하나 있었습니다. 전형적인 DP문제로 동전거슬러주기, 배낭에 제일 물건을 많이 넣는 방법 찾기 종류의 문제라 쉽게 풀었던 기억이 납니다.

한동안은 DP문제를 쭉 풀어봅시다.

num = int(input())
dp = [0]*(12)
dp[1] = 1
dp[2] = 2
dp[3] = 4
for i in range(4,12):
    dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
for i in range(num):
    print(dp[int(input())])

주어진 조건에서 n의 크기가 11이하로 굉장히 작습니다. 그래서 for문으로 11까지 전체를 구하고 바로 입력을 받을때마다 출력했습니다. 다만 인덱스를 편하게 처리하기 위해서 1칸을 더 크게 만들었습니다.