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

C++로 구현하는 두 정수 기반 짝수-홀수 턴 게임: O(1) 최적화 풀이

이 문제에서는 세 개의 정수 A, B, T가 주어지며, 두 개의 정수를 활용하는 짝수-홀수 턴 게임을 진행하는 프로그램을 작성하는 것이 목표입니다.

입력 값의 의미와 게임 규칙

  • T : 게임의 총 턴 수를 나타냅니다.
  • A : 플레이어 1의 값을 나타냅니다.
  • B : 플레이어 2의 값을 나타냅니다.

현재 턴 번호가 홀수이면 A의 값이 2배가 되고, 턴 번호가 짝수이면 B의 값이 2배가 됩니다. 모든 턴이 종료된 후 최종적으로 max(A, B) / min(A, B) 값을 계산하여 반환해야 합니다.

예제로 문제 이해하기

입력 : A = 3, B = 4, T = 3

출력 : 1

설명 :

1번째 턴 : 턴 번호가 홀수이므로 A가 2배가 됨 → A = 6
2번째 턴 : 턴 번호가 짝수이므로 B가 2배가 됨 → B = 8
3번째 턴 : 턴 번호가 홀수이므로 A가 2배가 됨 → A = 12

모든 턴이 끝난 후의 값은 A = 12, B = 8입니다.

max(A, B) = max(12, 8) = 12
min(A, B) = min(12, 8) = 8
max(A, B) / min(A, B) = 12 / 8 = 1 (정수 나눗셈)

풀이 접근 방법

1. 단순 시뮬레이션 방식

가장 직관적인 방법은 T번의 턴을 모두 반복하면서 A와 B의 값을 실제로 갱신한 뒤, 마지막에 max(A, B) / min(A, B)를 계산하는 것입니다. 이 방법은 O(T)의 시간이 걸리므로 T가 매우 큰 경우에는 비효율적일 수 있습니다.

2. 최적화된 수학적 접근

턴을 하나하나 시뮬레이션하지 않고도 결과를 바로 도출할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

T가 짝수인 경우 : A와 B는 정확히 같은 횟수(N = 2T/2)만큼 곱해집니다. 즉, 새로운 값은 각각 N*A와 N*B가 되며, 공통 인수 N이 약분되기 때문에 결괏값은 항상 일정합니다.
결괏값 = max(A, B) / min(A, B)

T가 홀수인 경우 : A는 한 번 더 곱해져 2*N*A가 되고, B는 N*B가 됩니다(N = 2(T-1)/2). 따라서 결괏값은 다음과 같습니다.
결괏값 = max(2A, B) / min(2A, B)

정리하면 문제의 최종 결과 max(A, B) / min(A, B)는 다음과 같습니다.

T가 짝수일 때 : max(A, B) / min(A, B)
T가 홀수일 때 : max(2*A, B) / min(2*A, B)

이 접근 방식은 반복문 없이 상수 시간 O(1) 안에 정답을 구할 수 있다는 점에서 훨씬 효율적입니다.

풀이 동작을 보여주는 프로그램

예제 코드

#include <iostream>
using namespace std;

int EvenOddGame(int A, int B, int T) {

    if (T % 2 == 0)
        return (max(A, B) / min(A, B));
    else
        return (max(2*A, B) / min(2*A, B));
    return -1;
}

int main() {

    int A = 3, B = 2, T = 3;
    cout<<"짝수-홀수 게임의 반환값은 "<<EvenOddGame(A, B, T);

}

출력 −

짝수-홀수 게임의 반환값은 3