백준 9095번 다이나믹 프로그래밍 -python

다이나믹 프로그래밍 문제 중 재미있게 풀었던 것을 가져왔다.

---

문제 9095

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

9095번: 1, 2, 3 더하기

---

 

풀이

다이나믹 프로그래밍이 하위 문제로 상위 문제를 풀 수 있는 기법이기 때문에

제일 작은 수들을 이용하여 그다음 큰 수를 계산할 수 있을 경우를 찾아본다.

 

1, 2, 3, 4 케이스를 적어보고 1, 2, 3을 이용하여 4를 만드는 방법을 생각하면 풀 수 있다.

 

점화식은 A(n) = A(n - 1) + A(n - 2) + A(n - 3) 

 

테스트 케이스에 4가 들어왔다고 생각하면

 

 A(4) = A(3) + A(2) + A(1)

 

3의 경우의 수   여기에 1을 더하면

1+1+1               1+1+1+1

1+2                   1+2+1

2+1                   2+1+1

3                       3+1

2의 경우의 수   여기에 2을 더하면

1+1                   1+1+2

2                       2+2

1의 경우의 수   여기에 3을 더하면

1                       1+3

 

이렇게 중복없이 4에 대한 경우의 수가 나오게 된다.

 

1부터 11 까지이니깐

계산값을 저장해둘 곳을 만들고

d = [0] * 12
d[1] = 1
d[2] = 2
d[3] = 4

1, 2, 3 경우는 점화식이 통하지 않으니 미리 정의를 해둔다.

 

점화식을 구현할 때는 반복문을 사용할텐데 4부터 11까지 반복해주면 된다.

for j in range(4, 12):
  #점화식 각 경우의 수에 1 또는 2 또는 3을 뺀 것과 같다.
  d[j] = d[j - 1] + d[j - 2] + d[j - 3]

완성본

n = int(input())

array = []
for i in range(n):
  array.append(int(input()))

d = [0] * 12
d[1] = 1
d[2] = 2
d[3] = 4

for j in range(4, 12):
  #점화식 각 경우의 수에 1 또는 2 또는 3을 뺀 것과 같다.
  d[j] = d[j - 1] + d[j - 2] + d[j - 3]
    
for k in range(n):
  print(d[array[k]])