[구름톤 챌린지 #11] 통증 (2)

문제11. 통증 (2)

구름LEVEL

---

---

문제 해결 방법

저번주 챌린지 문제였던 "문제8. 통증"에서 조건이 더 일반화된 문제이다. 예전의 문제는 회복 수치가 고정되어있었고, 서로 배수 관계였기 때문에 그리디 알고리즘을 적용할 수 있었다. 오늘 문제는 회복 수치가 고정되어있지 않고 배수 관계가 아니라는 것에 집중해야한다.

예전과 같은 유형의 문제이기 때문에, 큰 문제를 작은 문제로 쪼개어서 풀 수 있다는 최적 부분 구조를 만족한다. 다만, 탐욕적 선택 특성은 만족하지 않는다. 이럴 때 가장 먼저 떠올릴 수 있는 방법은 재귀이다. 생략이 많지만, 아래와 같은 재귀 함수를 적용하면 어렵지 않게 풀 수 있다.

def recur(n):
  return min(recur(n-a)+1, recur(n-b)+1)

하지만, 재귀를 이용했을 때에는 많은 경우, 재귀의 깊이가 너무 깊어지는 RecursionError를 겪거나, 이미 결과를 냈던 조건을 반복해서 탐색하게 되어 시간 초과를 겪게 된다.

 

그래서 필요한 것이 DP이다. DP(=Dynamic Programming, 동적 프로그래밍)에서 가장 중요한 원리는 Memoization이다. 이미 결과를 낸 것은 기억해두었다가 다시 탐색할 때 꺼내쓰는 것이다. 역시 생략이 많지만 아래 코드와 같이 dp_table에 값을 저장해두고, 이미 값이 저장되어있다면 꺼내오는 방식을 사용한다면, 시간을 단축할 수 있다. 이처럼 큰 값부터 탐색을 시도하되, 결과를 구할 때 필요한 작은 값이 아직 저장되어 있지 않다면, 그 작은 값을 우선적으로 탐색을 하는 방식이 top-down dp(하향식 dp)이다.

max_value = sys.maxsize

dp_table = [max_value for i in range(n)]

def dp(n):
  if dp_table[n] != max_value:
    return dp_table[n]
  else:
    dp_table[n] = min(dp(n-a)+1, dp(n-b)+1)
    return dp_table[n]

다만 위와 같은 코드는 아직 재귀의 깊이가 깊어질 수 있다는 문제를 해결해내지 못했다. 한 가지 생각해볼 수 있는 점은, 큰 값부터 탐색을 시도해도 어차피 작은 값을 탐색하러 갈 수 밖에 없다는 점이다. 그렇다면 작은 값부터 탐색할 수는 없는지가 궁금해질 것이다. 그게 바로 bottom-up dp이다!

 

위 문제를 예시로 들면, dp_table[i]를 i의 수치를 치료하는 데 드는 아이템의 최솟값이라고 할 때, 임의의 i에 대해서 dp_table[i] 값을 알고 있다면 dp_table[i+a]와 dp_table[i+b]를 알 수 있다(dp_table[i] + 1). 이제, 우리가 처음에 정보를 알 수 있는 곳부터 시작해서 우리가 목표로 하는 결과를 얻어낼 때까지 거슬러 올라가면서 새로 얻어낸 정보를 dp_table에 업데이트 해주기만 하면 된다!

 

위 내용을 코드로 구현하면 아래와 같다.

import sys

n = int(input())
a, b = map(int, input().split())

dp_table = [sys.maxsize for i in range(n+1)]

if a <= n:
	dp_table[a] = 1
if b <= n:
	dp_table[b] = 1

for i in range(0, n):
	if dp_table[i] == sys.maxsize:
		continue
	
	if i+a <= n:
		dp_table[i+a] = min(dp_table[i+a], dp_table[i]+1)
		
	if i+b <= n:
		dp_table[i+b] = min(dp_table[i+b], dp_table[i]+1)

if dp_table[n] == sys.maxsize:
	print(-1)
else:
	print(dp_table[n])