[백준 알고리즘] 1072번 게임(Java) 문제 풀이

2 초

128 MB

37727

8934

6601

23.770%

문제

김형택은 지금 몰래 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

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

1072번: 게임

문제에 대한 이해

문제를 자세히 보면 게임이 진행함에 따라 "형택이는 앞으로의 모든 게임에서 지지 않는다." 라는 말이 있다. 즉, 게임 1번을 할때마다 모두 이긴다. X가 1 늘어나면 Y도 1이 늘어난다.

어떻게 풀 것인가?

처음에는 단순 브루트포스로 풀었다 하지만...

계속해서 메모리 초과가 발생하여, 문제에 대한 접근이 틀렸다는 것을 알았다.

 

이 문제는 이분 탐색에 대한 것을 물어보는 것이였다.

 

이분 탐색이란,

이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.

무엇을 절반씩 좁혀 가야할까?

 

문제를 보면 X의 범위가

• 1 ≤ X ≤ 1,000,000,000

라는 것을 알 수 있다. 즉, X의 범위를 좁혀가며 확률을 계산하고, 이에따라 게임을 최소 몇 판 더 해야하는지에 대한 값을 출력하면 된다.

시간복잡도

O(log10^9)

공간복잡도

O(N)

풀면서 놓쳤던점

문제를 읽고 단순하게 생각했다. 공간복잡도에 대해서 많이 생각하지 못한 점이 문제였다.

이 문제를 통해 얻어갈 것

이분탐색

내 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 백준알고리즘 1072번 게임
public class Main {
    static int X, Y, Z;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        X = Integer.parseInt(st.nextToken());
        Y = Integer.parseInt(st.nextToken());
        Z = getPercent(X,Y);

        int result = -1;
        int left = 0;
        int right = (int) 1e9;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (getPercent(X + mid, Y + mid) != Z) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(result);
    }

    static int getPercent(int x, int y) {
        return (int) ((long) y * 100 / x);
    }
}