[알고리즘 문제 풀이][DP] 백준 9095번 - 1, 2, 3 더하기

백준 10989번 1, 2, 3 더하기 문제입니다.

(DP 문제)

 

- 문제 설명: https://www.acmicpc.net/problem/9095

- 문제 풀이:

 

정수를 1과 2와 3의 합으로 나타내야합니다. 본 문제에서 4를 나타내는 방법을 표현한 것을 보면 순서가 상관 있는 것을 볼 수 있습니다. (1 + 3 과 3 + 1 을 따로 침)

 

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

 

저는 이 문제를 DP를 공부하기 위해서 풀었기 때문에, 큰 범위부터 작은 범위로 줄여나가려고 했습니다. 예를 들어, 위에 주어진 값을 끝에가 1이 더해진 것과, 2가 더해진 것과 3이 더해진 것으로 묶을 수 있습니다. 그러면 이 문제는 4를 표현하는 방법을 구하는 것은 3을 표현하는 방법 (여기에 +1 하면 4가 되니까) + 2를 표현하는 방법 (+2 하면 되니까) + 1을 표현하는 방법 (+3 하면 되니까) 의 합을 구하면 되는 것입니다. 따라서 아래와 같이 코드를 작성하였습니다.

 

- 코드: 

memo = [0] * 20

def dp(n):
    if n == 1:
        return 1
    if n == 2: # 1+1 / 2
        return 2
    if n == 3:
        return 4 # 1+1+1 / 2+1 / 1+2 / 3

    if memo[n]:
        return memo[n]

    memo[n] = dp(n-1) + dp(n-2) + dp(n-3)
    return memo[n]

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

DP 를 풀 때, 이미 구한 값을 또 구하지 않도록 memoization 하는 것이 중요하기 때문에, memo 라는 배열을 두고, 이미 구한 값은 저장될 수 있도록 하였습니다.

 

그런데, 이 문제는 단순히 1, 2, 3 을 뺀 숫자들의 합이기 때문에 위와 같이 재귀 형식으로 하지 않고, for 문으로 간단하게 표현할 수도 있습니다.

import sys
r = sys.stdin.readline

arr = [0] * 11
arr[0] = 0
arr[1] = 1
arr[2] = 2
arr[3] = 4
for i in range(4, 11):
    arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3]
for _ in range(int(r())):
    num = int(r())
    print(arr[num])

 

- 실수 포인트 & 반례:

1. 본 문제는 특별한 반례가 없습니다.

많은 분들이 TC 처리에서 런타임 에러 등이 발생하는 것은 확인할 수 있습니다. 

TC 마다 배열이나 변수들이 잘 초기화되고 있는지 등을 확인해주시면 됩니다.

https://www.acmicpc.net/board/view/58808