99클럽 코테 스터디 1일차 TIL - 게임 : 백준 1072번 - 이분탐색

 

1. 오늘의 문제

게임 - 백준 1072번

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

 

 

 

2. 공부한 내용

2 - 1. 백준 사이트 적응

오랜만에 백준 문제 풀어서 적응하는 시간이 걸렸다. 

마지막으로 백준 문제 제출해본지가 1년이 넘은 듯 한데...

문제 다 풀고 제출했더니 컴파일 에러가 발생하여(분명 인텔리제이에서는 실행 잘 됫었는데?)

class 이름이 Main 이어야 한다는 걸 깜빡했다.

 

2 - 2. 게임 - 백준 1072번

---

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

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

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

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

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

 

예제 입력 1 복사

10 8

예제 출력 1 복사

1

---

첫 날 이고 하니 가벼운 구현 문제라 생각하고 풀고 제출을 했다.

그랬더니 문제가 틀렸다네?

제시된 예제 입력 5개를 다 통과했는데 왜 틀렸다고 할까...

 

그래서 힌트를 봤다.

 

"이분 탐색"

 

아 이거 시간복잡도가 문제가 되는거구나?

들어올 수 있는 입력이

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

이렇게 되니까 승률이 바뀌는지 체크하려면 오래걸리는거구나?

이분 탐색 요새 공부 안해서 구현방법 까먹었는데 어떡하지?

그래서 예전에 풀었던 문제를 들춰보기 시작했다.

 

2 - 3. 내가 푼 답안

import java.util.Scanner;

// 백준 1072번 게임
public class Main {

    static int N;
    static int M;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        int currentPercent = calculateWinningPercent(N, M);

        int answer = -1;
        int left = 0;
        int right = (int) 1e9;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (calculateWinningPercent(N + mid, M + mid) != currentPercent) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(answer);

    }
}

 

2 - 4. 이분탐색 복습

이분탐색은 그냥 반씩 뚝뚝 잘라서 탐색한다고 보면 된다.

완전 탐색, 브루트 포스 방식은 처음부터 끝까지 탐색을 수행하다가 승률이 바뀔 때 정답이 나오므로 

시간복잡도로 따지면, O(N) 이다.

O(N)은 꽤 괜찮은 시간복잡도이긴 하지만, 입력으로 큰 수가 들어오면 타임아웃이 나올 수 있다.

이분탐색은 반씩 자르면서 탐색을 하니까 O(logN) 시간복잡도를 갖는다.

2010 Thomas J Cortina, Carnegie Mellon University

사진을 보면 O(N) -> O(logN) 으로 시간복잡도가 바뀌면 연산 수가 대폭 줄어든다는 것을 확인할 수 있다.

 

3. 소감

첫 날은 dfs, bfs 중에 하나 나올줄 알았는데 이분탐색이라니...

생각지도 못했다.

다음번에 나오면 후다닥 풀어버려야지

 

https://github.com/Griotold/dfs-bfs

GitHub - Griotold/dfs-bfs: DFS, BFS 정복하기