[구름톤 챌린지 #8] 통증

문제8. 통증

구름LEVEL

---

---

문제 해결 방법

사용해야하는 회복 아이템의 총 개수를 최소로 하는 방법을 찾아야 한다.

각 아이템의 회복 수치를 보면 붕대(bandage)는 1, 약(medicine)은 7, 진통제(painkiller)는 14의 수치를 회복시켜 준다.

 

중요한 점은 서로가 서로의 배수라는 점이다. 같은 수치를 회복한다고 했을 때, 진통제를 사용하는 대신 약을 사용하면 2배 더 많은 회복 아이템을 사용해야 한다. 약을 사용하는 대신 붕대를 사용하면 7배 더 많은 회복 아이템을 사용해야한다. 심지어 진통제 대신 붕대를 사용하면 14배 더 많은 회복 아이템을 사용해야 한다.

 

즉, 사용해야하는 회복 아이템의 총 개수를 최소로 하려면, 진통제를 가능한 많이 사용하고, 반대로 붕대는 최소한으로 사용해야한다.

 

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

n = int(input())

bandage_count = 0
medicine_count = 0
painkiller_count = 0

painkiller_count += n // 14
n %= 14

medicine_count += n // 7
n %= 7

bandage_count += n // 1

print(painkiller_count + medicine_count + bandage_count)

---

그리디 알고리즘을 적용하여 최적해를 보장할 수 있는 조건

위 문제는 현재 사용할 수 있는 아이템 중, 가장 크게 회복시켜주는 아이템만을 계속해서 선택하는 방식으로 해결되었다. 이처럼 당장 가장 큰 이득이 될 수 있는 방식을 따라가는 알고리즘을 그리디 알고리즘(Greedy Algorithm)이라고 부른다. 당장의 이익만 고려하면 된다는 점에서 구현이나 이해가 간단해진다는 점이 그리디 알고리즘의 장점이다. 다만, 그리디 알고리즘을 통해 도출해낸 답이 최적의 답인 경우는 그렇게 많지 않다.

 

당장 위의 문제에서 각 아이템의 회복 수치를 조금만 조정해도 코드를 통해 나온 답이 정답과 멀어지게 된다. 예를 들어 약의 회복 수치를 8로 바꿔보자. 총 16 의 체력을 회복해야 한다고 했을 때, 정답은 8 + 8 = 16 으로 2 지만, 그리디 알고리즘을 적용하면 14 + 1 + 1 = 16 으로 3 을 얻게 된다.

 

그렇다면 그리디 알고리즘을 적용해서 최적의 답을 보장할 수 있는 조건은 무엇일까? 두 가지의 조건이 있다.

1. Optimal Substructure(최적 부분 구조): 큰 문제를 작은 문제들로 쪼갬으로써, 답을 구할 수 있다는 것을 의미한다.
2. Greedy Choice Property(탐욕적 선택 특성): 작은 문제들에서 최적인 답을 구했을 때, 그것이 전체 문제의 최적으로 이어진다.

위의 문제는 최적 부분 구조와 탐욕적 선택 특성을 모두 만족한다. 예를 들어 18 의 체력을 회복한다고 할 때, [우선 진통제로 14 의 체력을 회복 + 나머지 것들을 이용해서 4 의 체력을 회복] or [우선 약으로 7 의 체력을 회복 + 나머지 것들을 이용해서 11 의 체력을 회복] 과 같이 단계별로 문제를 풀어나갈 수 있으므로 최적 부분 구조를 만족한다. 그리고 각 단계에서의 최적의 답(가능한 큰 단위의 아이템을 이용해 회복)이 전체 문제의 최적으로 이어진다(서로가 서로의 배수이기 때문). 따라서 그리디 알고리즘을 적용했을 때 최적의 답을 구해낼 수 있다. 이해를 돕기 위해 위 문제를 조금 더 그리디 알고리즘스럽게 표현한 코드는 아래와 같다.

def greedy(n):
    if n == 0:
        return 0

    # 14보다 크다면 14를 사용
    if n > 14:
        return greedy(n-14) + 1
    # 7보다 크다면 7을 사용
    if n > 7:
        return greedy(n-7) + 1
    # 7보다 작다면 1을 사용
    else:
        return greedy(n-1) + 1

n = int(input())
print(greedy(n))

 

최소 신장 트리 같은 복잡한 문제가 아닌, 위와 같이 단순히 숫자를 이용하는 문제에서는 각 단위가 서로의 배수가 되는지를 확인하면 그리디 알고리즘으로 최적해를 보장할 수 있으니, 앞으로는 단위를 보고 그리디 알고리즘을 적용해도 될지를 판단해보자.