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

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

9095번: 1, 2, 3 더하기

 

1. 내가 작성한 코드

t = int(input())

for i in range(t):

  n = int(input())

  d = [0,1,2,4] #1,2,3을 만들 수 있는 경우의 수

  if n > 3:

    d = d + [0] * (n-3)

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

  print(d[n])

 

1. 수를 만들 때는 1,2,3만을 사용할 수 있다.

 

1을 만들 수 있는 방법 => (1) => 1가지

2를 만들 수 있는 방법 => (1,1),(2) => 2가지

3을 만들 수 있는 방법 => (1,1,1),(1,2),(2,1),(3) => 4가지이다.

 

2. 다이나믹 프로그래밍을 할 것이기 때문에 위 1,2,4를 DP list에 넣어준다. => d = [0,1,2,4]

=> for문과 출력을 용이하기 위해서 0의 자리에는 0을 넣어줬다.

 

3. n이 3보다 작거나 같을 때는 그냥 d[n] 값을 출력하면 된다.

 

4. n이 3보다 클 때는 반복문을 돌린 후 d[n]값을 출력하면 된다.

 

여기서 반복문이 

 

for i in range(4, n+1):

  d[i] = d[i-1] + d[i-2] + d[i-3]

 

인 이유를 알아보자.

 

4.1 n = 4인 경우

 

앞서 1,2,3을 만들 수 있는 경우는 아래와 같다고 정의했다.

d[1]  1

d[2] 1,1 / 2

d[3] 1,1,1 / 2,1 / 1,2 /3

 

4를 만들 수 있는 경우는

 

d[4] 3+1 => d[1] 2+1+1 => d[2] 2+2 1+1+1+1 => d[3] 1+2+1 1+1+2 1+3

으로 d[1] + d[2] + d[3] 총 7이 된다.

 

즉 3,2,1를 각각 더해서 만들 수 있는 경우의 수가 d[1],d[2],d[3] 이라서

 

위와 같은 점화식이 나오게 되는 것이다.

 

위 점화식을 4부터 n까지 반복함으로써 d[n]을 출력하면 된다.