[백준 - C#] 1072번 게임

문제링크

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

1072번: 게임

 

문제

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

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

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

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

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

조건

시간제한 : 2초
메모리 제한 : 128 MB

입력

1 ≤ X ≤ 1,000,000,000
0 ≤ Y ≤ X
각 줄에 정수 X와 Y가 주어진다.

출력

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

 

문제정리

1. 게임 횟수 : X랑 이긴 게임 수 : Y가 주어질 때 승률은 Z이다.
2. 이제부터 형택이는 한번도 지지 않을 것이다.
3. 형택이가 게임을 최소 몇 번 더 해야 승률 Z가 변하는지 구하세요.
4. 1 ≤ X ≤ 1,000,000,000  //  0 ≤ Y ≤ X

이번 문제의 경우 처음 주어진 승률 Z에서 몇번 더 게임을 이겨야 승률이 변하는지 구하는 문제입니다.

예를 들어 처음 승률이 53판 47승으로 88%라면 승률 89%가 될 때까지 몇번 더 해야되는지 구하면 되는 것입니다.

저의 경우 X의 크기가 너무 커서 이분 탐색으로 풀이를 진행 하였는데 주의 할점으로 두가지가 있습니다.

 

첫 번째로 99%는 승률 100%가 될 수 없다는 것이고

두 번째로는 부동소수점으로 살짝에 오차가 있다는 것입니다.

( 1072번에 대한 질문 검색에 57.9999999 와 58의 차이를 설명해주신 분이 있는데 바로 이해가 되었습니다. )

아래 코드의 경우에도 X랑 Y의 변수 타입을 int로 바꿔주게 되면 마지막 예제 문제가 틀리게 나옵니다.

 

코드를 보며 주의할 점을 생각하며 코딩 해보시기 바랍니당 ㅎㅎ 

 

C# 코드

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    string[] input = reader.ReadLine().Split();
    long X = long.Parse(input[0]); // 게임 횟수
    long Y = long.Parse(input[1]); // 이긴 게임
 
    //부동소수점 오차주의
    int avg = (int)(Y * 100 / X);
 
    long start = 0;
    long end = (int)1e9;
    long middle;
    long result = -1;
 
    // start가 end보다 커지는 순간 프로그램 종료
    while (start <= end)
    {
        // 이분탐색 중간 값
        middle = (start + end) / 2;
 
        // 추가로 한 게임횟수의 평균값이랑 기존 평균값을 비교
        // 이긴횟수를 증가시키면 게임횟수도 증가 시켜줘야 합니다.
        if ((int)((Y + middle) * 100 / (X + middle)) != avg)
        {
            result = middle;
            end = middle - 1;
        }
        else
        {
            start = middle + 1;
        }
    }
 
    writer.WriteLine(result);
 
    writer.Close();
    reader.Close();
}

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.