문제 설명 #

목표: 주어진 hp를 가장 적은 수의 개미를 사용해 0으로 만드는 것입니다. 사용할 수 있는 개미는 다음과 같습니다:

장군개미: 5 병정개미: 3 일개미: 1

문제 #

  • 적군의 체력이 인자로 주어집니다.

체력이 6 주어진다면 대략 아래와 같이 개미들을 출동시킬 수 있습니다.

  • 장군개미 하나, 일개미 하나
  • 병정개미 둘,
  • 일개미 여섯

위 예시들 중 개미의 수가 가정 적은 장군개미 하나, 일개미 하나를 선택하면 됩니다.

후술 #

접근법 #

이 문제는 주어진 체력에 대해 얼마나 효율이 좋은 개미를 몇마리 투입 할 수 있는가? 에 대한 질문으로 다시 생각해볼 수 있습니다.

주어진 체력이 30인 경우, 30 / 5라는 나눗셈에 의해 장군개미 6마리로 체력을 0으로 만들 수 있습니다. 31인 경우, 31 / 5 = 6이고 남은 체력은 1입니다.

이제 반복되는 패턴이 보이게 됩니다. 주어진 개미들을 배열로 세워두고 [5, 3, 1] 배열에 대해 반복문을 순회하면서 각 개미가 얼만큼 체력을 나눌 수 있는가?를 계산하면 됩니다.

풀이 #

필요한 개미의 수를 누산하는 count 변수를 생성합니다. -> let count = 0; 개미들을 공격력이 높은 순서대로 배열로 만들고 -> [5, 3, 1] 배열을 순회하며 인자로 주어지는 hp에 대해 나눗셈 연산을 진행합니다.

  • 배열은 내림차순 정렬이 되어 있어 최소한의 필요 개미를 골라낼 수 있습니다.
  • 배열이 주어지고 배열을 정렬해야 하는 경우 O(1)이 아닌 O(log)의 시간을 가질 것입니다.

인자로 체력 6이 주어질 경우

6 / 5에 대한 연산이 진행됩니다. hp에 대해 장군 개미가 몇이 필요한지 알 수 있게됩니다.

count라는 변수에 누산해줍니다.

이제 남은 hp는 1이 되어야합니다. hp의 값을 초기화해줍니다. -> hp = hp % ant;

function solution(hp) {
  let count = 0;
  const ants = [5, 3, 1];
  for (const ant of ants) {
    if (!hp) break;
    const mountOfAnt = ~~(hp / ant);
    count += mountOfAnt;
    const restHp = hp % ant;
    hp = restHp;
  }
  return count;
}

solution(23); // 5

후술 #

  • 주어지는 인자의 hp 값에 따라 고정길이 3인 배열을 순회하므로 해당 알고리즘의 Big O notation은 O(1)입니다.

  • 고정길이의 배열을 순회하면서 매번 세 개미들 중 최적의 선택을 합니다.

    • 해당 선택은 이전 선택과 이후 선택을 고려하지 않습니다.

  • 예전에 풀었던 동전 문제도 위 문제와 같은 방식입니다.