[백준] 9095번 1, 2, 3 더하기(다이나믹 프로그래밍)(DP)(Python - 파이썬)

백준 9095번 문제입니다. (solved.ac)기준 실버 3 문제입니다.

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

9095번: 1, 2, 3 더하기

문제 접근

첫째 줄에 테스트 케이스 T가 주어지고 테스트 케이스 만큼 정수 n을 입력받습니다. n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력하면 되는 문제입니다. 처음에 DP로 접근하는 것이 어려웠는데 접근하고 나서는 간단한 점화식으로 문제를 해결할 수 있었습니다.

 1, 2, 3을 이용하여 1을 만드는 방법은 (1)으로 한 가지 방법 / 2를 만드는 방법은 (1+1), (2)으로 두 가지 방법 / 3을 만드는 방법은 (1+1+1), (1+2), (2+1), (3)으로 네 가지 방법이 있습니다.

4를 만들기 위해서는 1에서 3을 더하는 방법, 2에서 2를 더하는 방법, 3에서 1을 더하는 방법이 있습니다. 

1 = (1)

2 = (1+1), (2)

3= (1+1+1), (1+2), (2+1), (3)

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

따라서 d[n] = d [n-1] + d [n-2] + d [n-3]이라는 점화식을 발견할 수 있습니다.

2를 만드는 방법 +2 가 4를 만드는 방법 중 일부라면 (1+1) +2, (2) +2의 방법 말고도 (1+1) +1 +1, (2) +1 +1의 방법도 가능하지 않냐고 궁금하실 수도 있는데 3에서 1을 더해주는 과정에서 처리가 되기 때문에 2에서 +2 가 아닌 +1 +1의 개수를 포함시켜 준다면 중복 처리가 됩니다.

정답 코드

# 테스트 케이스를 입력 받음.
t = int(input())

# n의 11보다 작기 때문에 11개의 리스트를 생성
d = [0] * 11

# 1,2,3으로
# 1을 나타내는 방법은 1가지 (1)
# 2를 나타내는 방법은 2가지 (1+1),(2)
# 3을 나타내는 방법은 4가지 (1+1+1),(1+2),(2+1),(3)
d[1], d[2], d[3] = 1, 2, 4

# 발견한 점화식을 사용하여 d[n]에 정답값을 넣어 놓음.
for i in range(4, len(d)):
    d[i] = d[i - 1] + d[i - 2] + d[i - 3]

# 테스트 케이스만큼 반복
for _ in range(t):

    # 정수 n을 입력 받음.
    n = int(input())

    # 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력
    print(d[n])