C++의 게임에서 마지막 몬스터의 가능한 최소 최종 건강

문제 설명

N명의 몬스터가 주어지면 각 몬스터는 정수인 초기 체력 h[i]를 가집니다. 생명력이 0보다 크면 몬스터가 살아 있습니다.

매 턴마다 무작위 몬스터는 다른 무작위 몬스터를 죽입니다. 공격을 받은 몬스터의 생명력은 공격하는 몬스터의 생명력만큼 감소합니다. 이 과정은 하나의 몬스터가 남을 때까지 계속됩니다. 마지막 남은 몬스터의 가능한 최소 체력은 얼마입니까?

예시

입력 배열이 {2, 14, 28, 56}이면 첫 번째 몬스터만 나머지 3마리의 몬스터를 계속 공격할 때 마지막 몬스터의 최종 체력이 최소인 2가 되기 때문에 출력은 2가 됩니다.

알고리즘

아래 GCD 공식을 사용하여 최종 답을 얻을 수 있습니다. -

H(최소) =gcd(h1, h2, …, hn)

예시

#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