[백준] 9095번 1,2,3 더하기 - python

 

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

9095번: 1, 2, 3 더하기

문제 설명은 해당 링크에서 보면 되므로 하고 넘어가겠다.

 

풀이

이 문제는 단순하게 정수를 잘 나누기만 하면 쉽게 풀리는 문제이다. DP인게 힌트가 될 수 있는게 DP의 개념이 큰 문제를 작은 문제로 나누어 작은 문제를 해결해 큰 문제를 푸는 것이기 때문에 주어진 정수 N을 그보다 작은 수의 합으로 나누어 계산하면 된다.

그럼 어떻게 N을 나누면 결과를 얻을 수 있을까? 여기서 잘 생각해보면 사실 N보다 작은 수들의 경우는 이미 계산을 한 상태라고 할 수 있다. 즉 N-1에 1을 더하면 N이 나오고 N-2에 2를 더하면 N이 나오고 N-3에 3을 더하면 N이 나오므로 각 N-1, N-2, N-3이 만들어지는 경우의 수를 모두 더하면 1,2,3으로 N을 만들 수 있는 경우의 수가 나오는 것이다. 

 

코드

#백준 실버3 1,2,3 더하기 - dp
import sys
input=sys.stdin.readline

T=int(input())
N=[int(input().strip()) for _ in range(T)]

num_list=[1,2,4]#기본적으로 1,2,3에 해당하는 경우의 수
#10까지의 경우의 수를 미리 계산 -> 문제에서 N이 11보다 작다고 했으므로 미리 계산을 해 놓는 것이 좋다고 판단
for i in range(3,10):
  new=num_list[i-1]+num_list[i-2]+num_list[i-3]
  num_list.append(new)

#입력 받은 N을 가지고 계산한 값을 가지는 리스트에서 결과 찾기
for x in N:
  print(num_list[x-1])

내가 풀이한 코드인데 먼저 N=1,2,3인 경우는 미리 계산을 해서 리스트에 넣어둔다. 그리고 문제에서 N이 11보다 작은 정수라고 주어졌으므로 10까지만 계산을 하면 되기 때문에 미리 계산을 하는 것이 좋다고 판단하여 계산부터 진행을 했다. 그리고 입력받은 N을 가지고 리스트에서 해당 정수의 경우의 수를 출력만 하면 된다.