백준 9095 파이썬 - 1,2,3 더하기 - 동적 계획법, DFS

백준 9095 파이썬

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

9095번: 1, 2, 3 더하기

정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 알고리즘 문제입니다. 단, 위치의 중복까지 가능한 조건입니다.

예를 들어 4라는 정수를 만들 때

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

이렇게 위치의 중복까지 가능한 조건 입니다.

 

이 문제는 동적 계획법을 공부하기 위해 풀은 문제인데요... 문제를 해결하는 방법을 고민해 보면서 DFS를 사용하고 싶다는 생각이 많이 들었어요. 순열이나 조합을 구할 때 DFS를 사용해서 했던 기억이 있어서 먼저 떠올랐는데요... 두가지 방법 모두 아래의 원리를 사용했습니다.

• 정수 n이 되기 위해 (1,2,3)을 더한 합의 방법은... (1,2,3)을 각각 뺀 n-(1,2,3)을 더합 합의 방법을 전부 합산한 값이다

글로 설명하기에는 힘드니 아래 표를 보면 이해가 될것이다.

1	2	3	4
1	(1) + 1 2	(1) + 2 (1 + 1) + 1 (2) + 1 3	-3 위치에서 합 (1) + 3 -2 위치에서 합 (1 + 1) + 2 (2) + 2 -1 위치에서 합 (1 + 2) + 1 (1 + 1 + 1) + 1 (2 + 1) + 1 (3) + 1

피보나치 수열인데 3개씩 더하는 형식입니다.

 

 

Python 풀이 1

먼저 동적 계획법으로 문제를 해결한 풀이 입니다.

import sys
read = sys.stdin.readline

cache = [0] * 11
cache[1] = 1
cache[2] = 2
cache[3] = 4

for i in range(4, 11):
    cache[i] = sum(cache[i-3:i])

T = int(read())
for _ in range(T):
    print(cache[int(read())])

• 초기값을 1,2,3의 경우까지 먼저 캐시값에 넣어줍니다.
• 범위가 10까지 이기 때문에 미리 값들을 모두 구하고 리스트를 순회하도록 합니다.
  • i 부터 이전 3개까지 합산을 구한다.

 

Python 풀이 2

이번 풀이는 DFS를 이용한 풀이입니다.

import sys
read = sys.stdin.readline

def dfs(num):
    if arr[num] > 0:
        return arr[num]
    if num == 1:
        return 1
    elif num == 2:
        return 2
    elif num == 3:
        return 4
    else:
        arr[num] = dfs(num-1) + dfs(num-2) + dfs(num-3)
        return arr[num]
     
T = int(sys.stdin.readline())
for _ in range(T):
    l = int(read())
    arr = [0] * (l+1)
    print(dfs(l))

• 동적 계획법이랑 원리는 같습니다. 단 재귀를 통해서 구하는 차이만 있습니다.

미리 값들이 들어 있는 배열을 만들어서 해도되는데... 그럴려면 1,2,3에 대한 초기값을 배열에 직접 넣어 동적 계획법이랑 너무 같은 것 같아서 매번 다시 순회하는 형식으로 풀었습니다.