백준-9095번 1,2,3 더하기

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

DP란?

Divide-And-Conquer : Top-down approach

• 나누어진 부분들 사이에 서로 상관관계가 없는 문제를 해결하는데 적합
• 피보나치 알고리즘의 경우에는 나눈어진 부분들이 서로 연관이 있다.
• 즉, 분할정복식 방법을 적용하여 알고리즘을 설계하게 되면 같은 항을 한 번 이상 계산하는 결과를 초래하게 되므로 효율적이지 않다. 따라서 이 경우에는 분할정복식 방법은 적합하지 않다.

 Dynamic programming: bottom-up approach

• 큰 문제를 작은 문제로 나눈 다는 점은 Divde-And-Conquer와 동일하다.
• 그러나 작은 문제를 먼저 해결하고, 그 결과를 저장한 다음, 후에 그 결과가 필요할 때마다 다시 계산하는 것이 아니고 저장된 결과를 이용해 도출해낸다.
• 여기에서의 Programming → 해답을 구축하는데 배열(테이블)을 사용함을 의미한다.

---

 

전에 결과를 이용해서 원하는 결과를 도출해낸다는 DP의 정의에 따라 접근해보자.

먼저 1을 1,2,3의 합으로 나타내는 방법은 1 = 1 한 가지다.

다음 2를 1,2,3의 합으로 나타내면 2 = 1+2 , 2 두 가지이다.

반복해가며 규칙을 발견해보자.

 

1	1	1개
2	1+1 2	2개
3	1+1+1 1+2 (2개) 3	4개
4	1+1+1+1 1+1+2 (3개) 2+2 1+3 (2개)	7개
5	1+1+1+1+1 1+1+1+2 (4개) 1+2+2 (3개) 1+1+3 (3개) 3+2 (2개)	13개
6	1+1+1+1+1+1 1+1+1+1+2 (5개) 1+1+2+2 (6개) 1+1+1+3 (4개) 2+2+2 2+3+1 (6개) 3+3	24개
7	-	44개

 

살펴보게 되면 전에 구했던 숫자들이 다음 숫자를 구성하는데 포함됨을 확인할 수 있다.

우선 1,2,3 인 경우는 기본으로 크게 규칙이 없이 기본으로 제공이 된다.

 

즉 A(1) = 1, A(2) = 2, A(3) = 4 이다.

 

A(4)인 경우를 살펴보게 되면, 이 경우에는 A(1) + 3, A(2) + 2, A(3) + 1로 이루어진다.

각 값을 만들어주기 위한 값에 추가로 숫자를 더해주면 되는 것이다.

 

점화식을 작성해보게 되면 A(n) = A(n-1) + A(n-2) + A(n-3) 이다.

 

 

이 결과를 바탕으로 코드를 작성해보자.

 

나는 처음엔 재귀로 작성하였다.

def dp(n):
    if(n == 1):
        return 1
    elif(n == 2):
        return 2
    elif(n == 3):
        return 4
    else:
        return(dp(n-1)+dp(n-2)+dp(n-3))
T=int(input())
for i in range(T):
    n = int(input())
    print(dp(n))

 

하지만 이렇게 작성하게 되면 계산량이 늘어나 시간초과가 발생할 수 있다.

다행? 이도 이번문제에서는 통과를 했으나 반복문이나, 리스트에 저장해가며 작성하는걸 추천한다.

 

이를 개선한 버전은 아래와 같다.

 

def dp(n):
    if n <= 3:
        return [0, 1, 2, 4][n]
        
    # n+1 크기의 리스트를 생성하고 초기값을 설정
    dp_list = [0] * (n + 1)
    dp_list[1] = 1
    dp_list[2] = 2
    dp_list[3] = 4
   
    # 4부터 n까지 값을 계산하여 리스트에 저장
    for i in range(4, n + 1):
        dp_list[i] = dp_list[i-1] + dp_list[i-2] + dp_list[i-3]
    return dp_list[n]

T = int(input())
for _ in range(T):
    n = int(input())
    print(dp(n))