C++로 풀어보는 마지막 몬스터의 최소 체력 문제 – GCD 활용법

문제 설명

N마리의 몬스터가 주어지며, 각 몬스터는 정수 형태의 초기 체력 h[i]를 가집니다. 체력이 0보다 큰 몬스터는 생존 상태로 간주됩니다.

매 턴마다 한 몬스터가 다른 몬스터를 무작위로 공격하며, 공격당한 몬스터의 체력은 공격한 몬스터의 체력만큼 감소합니다. 이 과정은 단 한 마리의 몬스터만 남을 때까지 반복됩니다. 이때 마지막까지 살아남은 몬스터의 최소 가능 체력은 얼마일까요?

예시

입력 배열이 {2, 14, 28, 56}이라면 출력 결과는 2입니다. 첫 번째 몬스터(체력 2)가 나머지 세 몬스터를 계속해서 공격하면, 마지막 몬스터의 최종 체력은 2가 되며 이것이 만들 수 있는 최솟값입니다.

알고리즘 접근 방식

이 문제는 의외로 간단하게 해결할 수 있습니다. 바로 모든 체력 값의 최대공약수(GCD)를 구하는 것입니다.

H(min) = gcd(h1, h2, …, hn)

그 이유는 다음과 같습니다. 몬스터 간의 공격은 본질적으로 체력의 뺄셈 연산과 같습니다. 유클리드 호제법의 성질에 따르면 두 수 a와 b에 대해 gcd(a, b) = gcd(a − b, b)가 성립하므로, 어떤 순서로 공격이 일어나더라도 최종적으로 남을 수 있는 체력은 모든 초기 체력의 최대공약수와 같아집니다.

C++ 코드 구현

#include <iostream>
using namespace std;

// 유클리드 호제법으로 두 수의 최대공약수를 구하는 함수
int gcd(int a, int b) {
   if (a == 0)
      return b;
   return gcd(b % a, a);
}

// 배열 전체의 최대공약수를 계산하여 최소 최종 체력 반환
int getPossibleHealth(int* health, int n) {
   int currentGcd = gcd(health[0], health[1]);
   for (int i = 2; i < n; ++i) {
      currentGcd = gcd(currentGcd, health[i]);
   }
   return currentGcd;
}

int main() {
   int health[] = { 4, 6, 8, 12 };
   int n = sizeof(health) / sizeof(health[0]);
   cout << "Possible final health = " << getPossibleHealth(health, n) << endl;
   return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.

Possible final health = 2

{4, 6, 8, 12} 네 값의 최대공약수는 2이므로, 마지막 몬스터가 가질 수 있는 최소 체력 역시 2가 됩니다.