[Programmers] #120837 - 개미 군단 [Java][C++][Python]

문제 링크

---

1. 아이디어

장군개미(공격력 5), 병정개미(공격력 3), 일개미(공격력 1)를 조합해 사냥감의 체력 hp를 정확히 채우는 데 필요한 최소 개미 수를 구하는 문제다. 장군개미를 $a$마리, 병정개미를 $b$마리 쓰면 나머지는 전부 일개미로 채워야 하므로 총 개미 수는 $a + b + (\text{hp} - 5a - 3b) = \text{hp} - 4a - 2b$로 쓸 수 있다. 즉 개미 수를 최소화하는 건 $4a + 2b$를 최대화하는 것과 같다.

장군개미를 한 마리 더 쓸 수 있을 때 한 마리를 더 쓰면 그만큼 병정개미나 일개미는 적게 써야 한다. 병정개미와 일개미 수의 조합에 따라 아래와 같은 경우들이 존재한다.

• 병정개미 0마리, 일개미 5마리 이상 → 일개미 5마리를 장군개미 한 마리로 대체할 수 있고 이 경우는 대체하는 것이 항상 이득이다.
• 병정개미 1마리, 일개미 2마리 이상 → 병정개미 1마리, 일개미 2마리를 장군개미 한 마리로 대체할 수 있고 이 경우는 대체하는 것이 항상 이득이다.
• 병정개미 2마리 이상 → 병정개미 2마리를 장군개미 한 마리와 일개미 한 마리로 대체할 수 있고 이 경우는 대체해도 손해가 아니다.

장군개미 한 마리를 더 쓸 수 있을 때 병정개미 수의 조합에 따라 어떤 경우에도 손해를 보지 않음을 알 수 있고, 따라서 교환 논증에 의해 최대한 장군개미로 대체하는 그리디한 선택을 할 수 있다. 같은 논리로 장군개미를 최대한 선택한 이후에는 일개미가 3마리 이상인 경우 대신 병정개미를 최대한 선택하는 것이 항상 최선이다.

---

2. 복잡도

접근	시간	공간
풀이	$O(1)$	$O(1)$

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public int solution(int hp) {
        return hp / 5 + hp % 5 / 3 + hp % 5 % 3;
    }
}

#include <bits/stdc++.h>
using namespace std;

int solution(int hp) {
    return hp / 5 + hp % 5 / 3 + hp % 5 % 3;
}

def solution(hp):
    return hp // 5 + hp % 5 // 3 + hp % 5 % 3

---