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

문제 링크

---

1. 아이디어

장군개미(공격력 5), 병정개미(공격력 3), 일개미(공격력 1)를 조합해 사냥감의 체력 hp를 정확히 채우는 데 필요한 최소 개미 수를 구하는 문제다. 장군개미를 a마리, 병정개미를 b마리 쓰면 나머지는 전부 일개미로 채워야 하므로 총 개미 수는 $a + b + (hp - 5a - 3b) = hp - 4a - 2b$로 쓸 수 있다. 즉 개미 수를 최소화하는 건 $4a + 2b$를 최대화하는 것과 같다. 장군개미를 하나 더 쓸 수 있을 때(나머지가 5 이상일 때) 실제로 하나 더 쓰면, 그만큼 병정개미로 채우던 몫이 줄어든다. 예를 들어 나머지가 $8$이면 병정개미 $2$마리($6$)로 채우고 남는 $2$는 일개미로 메워야 하는데, 장군개미를 하나 더 쓰면 나머지가 $3$으로 줄어 병정개미가 $1$마리만 있으면 되고 일개미도 필요 없다 — 병정개미가 $1$마리 줄어든 손실($2$)보다 장군개미를 더 쓴 이득($4$)이 커서 이득이다. 나머지가 $7$인 경우엔 장군개미를 더 쓰면 나머지가 $2$로 줄어 병정개미가 아예 필요 없어지는데(병정개미 $2$마리, 즉 손실 $4$), 이번엔 장군개미 이득($4$)과 정확히 같아 동률이다. 이렇게 나머지가 무엇이든 병정개미가 줄어드는 손실은 최대 $4$를 넘지 않고 장군개미의 이득은 항상 $4$이므로, 장군개미를 쓸 수 있는 한 최대한 쓰는 게 항상 손해가 아니다. 같은 논리로 남은 나머지를 병정개미로 최대한 채우는 것도 항상 이득이다(병정개미 하나는 일개미 셋보다 항상 적거나 같은 개수를 쓴다). 따라서 hp를 5로 나눈 몫만큼 장군개미를 쓰고, 그 나머지를 3으로 나눈 몫만큼 병정개미를 쓴 뒤, 마지막까지 남는 값은 1씩만 채울 수 있는 일개미로 메우면 전체 개미 수가 최소가 된다.

---

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)

---