[BAEKJOON] 백준 1072: 게임 (C#)

문제 링크

https://www.acmicpc.net/problem/1072

 

 

문제

김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.

이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.

게임 기록은 다음과 같이 생겼다.

• 게임 횟수 : X
• 이긴 게임 : Y (Z%)
• Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z=88이다.

X와 Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하는 프로그램을 작성하시오.

 

 

입력

각 줄에 정수 X와 Y가 주어진다.

 

 

출력

첫째 줄에 형택이가 게임을 최소 몇 판 더 해야하는지 출력한다. 만약 Z가 절대 변하지 않는다면 -1을 출력한다.

 

 

제한

• 1 ≤ X ≤ 1,000,000,000
• 0 ≤ Y ≤ X

 

 

 

통과한 답안

namespace _1072
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[] inputs = Console.ReadLine().Split(' ');
            long X = long.Parse(inputs[0]);
            long Y = long.Parse(inputs[1]);

            long Z = 100 * Y / X;

            if (Z >= 99)
            {
                Console.WriteLine(-1);
                return;
            }

            long left = 1;
            long right = 1000000000;
            long games = -1;

            while (left <= right)
            {
                long mid = (right + left) / 2;
                long newCnt = X + mid;
                long newWin = Y + mid;
                long newRate = 100 * newWin / newCnt;

                if (newRate > Z)
                {
                    games = mid;
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }

            Console.WriteLine(games);
        }
    }
}

 

현재 게임 횟수와 이긴 횟수가 주어지고 현재 승률을 정수 Z로 저장한 뒤

새로운 게임 횟수가 주어졌을 때, 승률이 변하는 경우에 필요한 최소 게임 수를 묻는 문제이다.

(단 새로운 게임은 모두 승리한다고 한다, 승률이 바뀌지 않는 경우에는 -1을 출력한다)

현재 게임 수는 X이고 이긴 횟수는 Y이므로

승률 Z는 100 * Y / X 로 표기할 수 있다.

 

우선 승률이 바뀌지 않는 경우를 찾아보면,

승률이 99% 이상인 경우에는 아무리 게임을 추가해도 승률이 바뀌지 않으므로,

승률을 구한 뒤에 Z가 99 이상인 경우에는 -1을 출력하고 종료되도록 한다.

 

이후에 승률이 변하는 경우를 구하면,

새로운 게임의 수를 c로 한다면

새로운 승률 newRate = 100 * (Y + c) / (X + c)가 된다.

이 값이 Z보다 큰 경우, 승률이 바뀌게 된 것이다.

따라서 이를 간단하게 구현하면 아래와 같이 구현할 수 있다.

 

int games = 0;

for (int i = 1; ; i++)
{
    long gameCnt = X + i;
    long winCnt = Y + i;
    long newRate = 100 * winCnt / gameCnt;

    if (newRate > Z)
    {
        games = i;
        break;
    }
}

 

하지만 이 경우에는 조건에 따라서 시간이 너무 오래 걸릴 수 있으므로

계산을 빠르게 작동하도록 코드를 수정해야한다.

 

이러한 조건에 맞는 결과를 찾는 경우에 개선할 수 있는 방법으로 이분 탐색을 적용할 수 있다.

위의 새로운 게임 수를 찾는 과정에서 for 문을 이용하여 1부터 찾았다면,

아래처럼 1부터 X의 최대 범위를 지정한 후에 이분 탐색을 적용하면 빠르게 해결할 수 있다.

long left = 1;
long right = 1000000000;
long games = -1;

while (left <= right)
{
    long mid = (right + left) / 2;
    long newCnt = X + mid;
    long newWin = Y + mid;
    long newRate = 100 * newWin / newCnt;

    if (newRate > Z)
    {
        games = mid;
        right = mid - 1;
    }
    else
    {
        left = mid + 1;
    }
}

 

최솟값과 최댓값을 지정한 후에 이들의 중간값을 이용하여

승률이 변하는 최소의 게임 수를 구할 수 있다.