문제
https://www.acmicpc.net/problem/9095
사용 언어
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 적용하기가 그렇게 어려웠는데...? 많은 공부가 필요해 보인다😅
'코딩 테스트 스터디 > 백준' 카테고리의 다른 글
[실버 I] 12852번. 1로 만들기2 (0) | 2022.04.28 |
---|---|
[실버 III] 1463. 1로 만들기 (0) | 2022.04.27 |
[실버 IV] 1158번. 요세푸스 문제 (0) | 2022.04.25 |
[골드 II] 4256번. 트리 (0) | 2022.04.08 |
[실버 III] 2630번. 색종이 만들기 (0) | 2022.04.07 |