코딩 테스트 스터디/백준

[실버 III] 9095번. 1, 2, 3 더하기

남쪽마을밤송이 2022. 4. 26. 21:49

 문제 

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

 

9095번: 1, 2, 3 더하기

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

www.acmicpc.net

 사용 언어 

Python3

 풀이 과정 

동적 계획법 문제는 점화식을 구하는 것이 중요하다는 걸 다시 한 번 깨달은 문제.

그리고 그 점화식을 구할 때에는 대개 마지막 경우의 수가 어떻게 되는지 생각해 보는게 쉽게 접근하는 방법인 것 같다.

1, 2, 3 숫자만 써서 합이 정수 n이 되는 조합을 만든다고 할 때, 마지막 더하기의 경우는

x + 1 = n
x + 2 = n
x + 3 = n

위 세 가지 경우밖에 없기 때문에 경우의 수는 n - 1을 구하는 경우, n - 2를 구하는 경우, n - 3을 구하는 경우를 모두 더해준 수인 것이다. 이걸 깨닫기만 하면 쉽게 해결할 수 있는 문제.

 제출 답안 

from sys import stdin

case = {1:1, 2:2, 3:4} # 각각 n이 1, 2, 3일 때
def add123(n):
    global case
    if n in case:
        return case[n]
    case[n] = add123(n-1) + add123(n-2) + add123(n-3)
    return case[n] # 1, 2, 3을 더해서 n이 되는 경우의 수

# case = [0, 1, 2, 4]
T = int(stdin.readline())
for i in range(T):
    n = int(stdin.readline())
    print(add123(n))

 다른 사람 답안 

나는 재귀를 이용해서 풀었는데 아무래도 더 많은 메모리와 시간을 소요할 것 같아 미리 공간을 할당하고 재귀를 사용하지 않은 풀이를 찾았다.

import sys
read = sys.stdin.readline

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

for i in range(4, 11): # 범위가 10까지 이기 때문에 미리 값들을 모두 구하고 리스트를 순회
    cache[i] = sum(cache[i-3:i])

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

출처: https://myjamong.tistory.com/302

그런데 의외로 메모리와 시간이 똑같게 나왔다... 범위가 작아서 차이가 없는 것 같기도 하고...

 

어쨌든 이 분의 설명을 보니 내 풀이는 동적 계획법이 아니라 DFS에 가까운 것 같다. 막상 DFS 공부할 때는 DFS 적용하기가 그렇게 어려웠는데...? 많은 공부가 필요해 보인다😅