Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 알고리즘 풀이 – 게임에서 승리하는 데 필요한 최소 플레이어 수 구하기

문제 설명

N개의 질문과 각 질문마다 K개의 선택지가 주어집니다(1 ≤ N ≤ 10⁹, 1 ≤ K ≤ 10⁹). 게임에서 반드시 승리하기 위해, 각 질문 i(1 ≤ i ≤ N)에 도전한 플레이어 수의 총합을 구해야 합니다. 단, 이 총합은 가능한 한 최소가 되어야 하며, 최종 답은 10⁹+7로 나눈 나머지로 출력해야 합니다.

여기서 중요한 조건은 한 번이라도 오답을 고르면 해당 플레이어는 즉시 탈락한다는 점입니다. 따라서 어떤 선택지가 정답이더라도 놓치지 않도록 충분한 인원을 배치해야 합니다.

예시

N = 5, K = 2인 경우 정답은 62입니다.

접근 방법

  • N번째(마지막) 질문을 확실히 통과하려면 K명의 플레이어가 필요합니다. 각자 서로 다른 선택지를 하나씩 고르면 되기 때문입니다.
  • (N−1)번째 질문을 통과하려면 K²명의 플레이어가 필요합니다.
  • 같은 방식으로 거슬러 올라가면, 1번째 질문을 통과하는 데는 KN명의 플레이어가 필요합니다.
  • 따라서 이 문제는 등비수열의 합 K + K² + … + KN을 구하는 문제로 환원되며, 그 값은 다음 공식으로 계산할 수 있습니다.
    K(KN − 1) / (K − 1)

모듈러 연산 처리

N과 K가 최대 10⁹까지 커질 수 있으므로 값을 직접 계산하는 것은 불가능합니다. 이를 해결하기 위해 두 가지 기법을 사용합니다.

  • 빠른 거듭제곱(분할 정복): O(log N) 시간에 KN mod (10⁹+7)을 계산합니다.
  • 페르마의 소정리: 10⁹+7은 소수이므로, (K−1)의 모듈러 역원은 (K−1)MOD−2 mod MOD로 구할 수 있습니다. 이를 통해 나눗셈을 곱셈으로 변환합니다.

C++ 구현 코드

#include <iostream>
#include <cmath>
#define MOD 1000000007
using namespace std;

long long int power(long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) {
            res = res * a;
            res = res % MOD;
        }
        b = b / 2;
        a = a * a;
        a = a % MOD;
    }
    return res;
}

long long getMinPlayer(long long n, long long k) {
    long long num = ((power(k, n) - 1) + MOD) % MOD;
    long long den = (power(k - 1, MOD - 2) + MOD) % MOD;
    long long ans = (((num * den) % MOD) * k) % MOD;
    return ans;
}

int main() {
    long long n = 5, k = 2;
    cout << "Minimum pairs = " << getMinPlayer(n, k) << endl;
    return 0;
}

출력 결과

위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.

Minimum pairs = 62

복잡도 및 참고 사항

빠른 거듭제곱 덕분에 전체 시간 복잡도는 O(log N)으로, N과 K가 10⁹처럼 매우 크더라도 즉시 계산할 수 있습니다. 다만 위 코드는 K = 1인 경우(공식의 분모가 0이 되는 경우)를 처리하지 않으므로, 실제 적용 시에는 K = 1일 때 정답이 N이라는 점을 별도로 처리해 주는 것이 안전합니다.