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

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

코드 작성

k = int(input())
for _ in range(k):
    d = [0, 1, 2, 4]
    n = int(input())
    for i in range(4, n+1):
        d.append(d[i-1]+d[i-2]+d[i-3])
    print(d[n])

코드  풀이

#1

이 문제는 다이나믹 프로그래밍으로 과거에 했던 연산을 누적하면서 수행해 나가는 문제이다.

우선

(1) 0을 1,2,3으로 표현하는 방법은 0가지

(2) 1을 1,2,3으로 표현하는 방법은 ’1‘ 1가지

(3) 2를 1,2,3으로 표현하는 방법은 ’1,1‘ ’2‘ 2가지

(4) 3을 1,2,3으로 표현하는 방법은 ’1,1,1‘ ’2,1‘, ’1,2‘, ’3‘ 4가지

(5) 4를 1,2,3으로 표현하는 방법은 ’1,1,1,1‘, ’2,1,1‘, ’1,2,1‘, ’3,1‘, ’1,1,2‘, ’2,2‘, ’1,3‘ 7가지

규칙을 살펴보면 4부터는 3의 표현방법에 1을 더하고, 2의 표현방법에 2를 더하고, 1의 표현방법에 3을 더하는 가지가 되므로 위 같은 코딩식이 나온다.

 

#2 다시 정리

색깔별로 보아야 한다. 우선 각각의 경우의 수 중,

젤 뒷자리가 1, 2, 3으로 끝나는 경우로 정리하였다.

5의 경우

i) 뒷자리가 1로 끝나는 경우는 4의 경우의 수에 1을 더한 값이다.

ii) 뒷자리가 2로 끝나는 경우는 3의 경우의 수에 2를 더한 값이다.

iii) 뒷자리가 3으로 끝나는 경우는 2의 경우의 수에 3을 더한 값이다.

 

즉 d[n] = d[n-1] + d[n-2] + d[n-3]의 값이 나온다.