[백준/DP/9095] 1, 2, 3 더하기

이미지 클릭시, 문제로 이동됩니닷 :)

간단한 문제이다.
테스트 케이스만큼 루프를 돌리고 1,2,3 세 개의 숫자의 합으로 n을 구하는 문제이다.

Test Case

# 1,2,3 으로 n을 만든다.

n = 1 일때, T = 1 // 1
n = 2 일때, T = 2 // 1+1, 2
n = 3 일때, T = 4 // 1+1+1, 1+2, 2+1, 3
n = 4 일때, T = 7 // 1+1+1+1, 1+1+2, 2+1+1, 1+2+1, 2+2, 1+3, 3+1
n = 5 일때, T = 13 

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

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

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

 

테스트 케이스를 구할 때 순서대로 작은 값 부터 나올 수 있는 경우의 수를 체크하여 구하는 게 가장 단순하고 쉬운 것 같다.
n=2 일때, 1은 몇 개 나올 수 있지?
n=3 일때, 1은 몇 개 나올 수 있지?
...

 

더 이상 나올 수 있는 방법이 없다고 생각이 들면,

 

n=2 일때, 2는 몇 개 나올 수 있지?
n=3 일때, 2는 몇 개 나올 수 있지?
...

 

DP 는 경우의 수만 잘 구할 수 있다면 사칙연산으로 풀이가 가능한 간단한 문제 인 것 같다.
(이게 제일 어렵긴하지만.. 다른 알고리즘과 비교한다면ㅎㅎ)

Sol

import sys
input = sys.stdin.readline

T = int(input())
dp = [0]*1001
dp[1] = 1
dp[2] = 2
dp[3] = 4

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

 

dp는 점화식이 생명이다.

 

n	1	2	3	4	5	6	7
경우의수	1	2	4	7	13	24	44

 

1~6까지 값을 구한 후 식을 찾만든다.

해당 식을 가지고 7을 대입 했을때 44가 나오면 된다.

 

대부분 DP 문제는 주어진 값만 나온다면 구한 점화식이 맞는 경우가 많은 것 같다.

 

DP는 초기값을 어떻게 주느냐가 가장 중요한 것 같다.

n=4 부터 구한 점화식이 유효하다.

 

DP는 초기값을 신중하게 생각하고 점화식을 만들자.