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

C++ 게임 문제: 0 이하로 줄일 수 있는 숫자 개수 구하기

양수로 이루어진 배열과 두 정수 A, B가 주어집니다. 두 명의 플레이어가 배열 속 숫자를 조작하는 게임을 진행하는데, 플레이어 1은 배열의 임의의 원소를 A만큼 감소시킬 수 있고, 플레이어 2는 임의의 원소를 B만큼 증가시킬 수 있습니다.

목표는 플레이어 1이 0 이하로 만들 수 있는 숫자의 개수를 구하는 것입니다. 플레이어 1이 선공을 하며, 한 번 0 이하로 줄어든 숫자는 플레이어 2가 더 이상 조작할 수 없습니다.

예제 입력 및 출력

예제 1

arr[] = { 1, 4, 5, 2 }, A = 2, B = 3

출력:

게임에서 0 이하로 줄일 수 있는 숫자의 개수: 1

설명: 플레이어 1이 줄일 수 있는 유일한 숫자는 1입니다. 선공에서 바로 −1이 되기 때문입니다. 나머지 숫자들은 플레이어 2가 값을 올린 후에는 A보다 커져서 더 이상 줄일 수 없습니다.

예제 2

arr[] = { 1, 4, 5, 2 }, A = 4, B = 4

출력:

게임에서 0 이하로 줄일 수 있는 숫자의 개수: 2

설명:

  • 선공에서 플레이어 1은 4를 0으로 줄입니다 → arr[] = [ 1, 0, 5, 2 ]
  • 플레이어 2는 1을 4로 올립니다 → arr[] = [ 5, 0, 5, 2 ]
  • 플레이어 1은 2를 −2로 줄입니다 → arr[] = [ 5, 0, 5, −2 ]

이후부터는 모든 숫자가 A보다 크고, 플레이어 2가 동시에 값을 올리고 있기 때문에 플레이어 1은 어떤 숫자도 0 이하로 만들 수 없습니다.

접근 방식

먼저 A > B인지 확인합니다. 참이라면 차례가 반복될수록 플레이어 1이 결국 배열의 모든 원소(N개)를 0 이하로 만들 수 있으므로 정답은 곧바로 배열의 길이가 됩니다.

A ≤ B라면 배열의 원소를 두 그룹으로 나누어 생각합니다.

  • C1: 플레이어 2가 B를 더해도 여전히 A보다 크지 않은(즉, arr[i] + B ≤ A) 숫자들의 개수 — 이 숫자들은 플레이어 2의 방해와 무관하게 언제든 0 이하로 만들 수 있습니다.
  • C2: 현재는 A 이하이지만, 플레이어 2가 B를 더하면 A보다 커지는 숫자들의 개수 — 이 숫자들은 두 플레이어가 경쟁적으로 조작하기 때문에 절반 정도만 0 이하로 만들 수 있습니다.

따라서 최종 답은 다음 공식으로 계산됩니다.

C = C1 + (C2 + 1) / 2

C2 그룹에서는 두 플레이어가 같은 숫자를 놓고 동시에 값을 올리고 내리기 때문에, 플레이어 2가 절반을 A보다 크게 만드는 동안 플레이어 1은 나머지 절반을 0 이하로 만들 수 있습니다. (C2 + 1)을 2로 나누는 이유는 홀수 개일 때 마지막 하나를 플레이어 1이 선공으로 가져갈 수 있기 때문입니다.

알고리즘 단계

  1. 양수로 이루어진 정수 배열과 두 변수 A, B를 입력받습니다.
  2. 함수 reduced_zero(int arr[], int size, int A, int B)는 게임에서 0 이하로 만들 수 있는 숫자의 개수를 반환합니다.
  3. 카운트를 0으로 초기화하고, 임시 변수 temp_1과 temp_2를 준비합니다.
  4. A > B이면 배열의 전체 길이 size를 바로 반환합니다.
  5. for 루프로 배열을 순회하면서 각 원소 arr[i]에 대해 다음을 확인합니다.
    • arr[i] + B ≤ A이면 temp_1을 1 증가시킵니다.
    • 그렇지 않고 arr[i] ≤ A이면 temp_2를 1 증가시킵니다.
  6. 루프가 끝나면 count = temp_1 + (temp_2 + 1) / 2를 계산합니다.
  7. count를 결과로 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int reduced_zero(int arr[], int size, int A, int B){
    int count = 0;
    int temp_1 = 0, temp_2 = 0;
    if (A > B){
        return size;
    }
    for(int i = 0; i < size; i++){
        if (A >= arr[i] + B){
            temp_1++;
        }
        else if(A >= arr[i]){
            temp_2++;
        }
    }
    int temp = (temp_2 + 1) / 2;
    count = temp + temp_1;
    return count;
}
int main(){
    int arr[] = { 3, 3, 1, 2, 4, 7, 1};
    int A = 4, B = 1;
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"게임에서 0 이하로 줄일 수 있는 숫자의 개수: "<<reduced_zero(arr, size, A, B);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

게임에서 0 이하로 줄일 수 있는 숫자의 개수: 7

마무리

이 문제는 모든 게임 과정을 일일이 시뮬레이션하는 대신, A와 B의 크기 관계와 각 원소가 어느 그룹에 속하는지만 파악하면 O(N) 시간 복잡도로 빠르게 해결할 수 있는 수학적 사고력 훈련에 좋은 알고리즘 문제입니다.