99클럽 코테 스터디 1일차 TIL + 백준1072 게임

 

 

간단한 문제였다. 

 

import java.util.Scanner;

public class Main {  

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        long all = scanner.nextLong();    // 전체 게임 횟수
        long wins = scanner.nextLong();   // 승리한 횟수
        scanner.close();

        long rate = (wins * 100) / all;  // 현재 승률 계산

        if (rate >= 99) {  
            System.out.println(-1);
            return;
        }

        long count = 0;
        while ((wins + count) * 100 < (rate + 1) * (all + count)) {
            count++;
        }

        System.out.println(count);
    }
}

 

자연어를 그냥 그대로 풀어서 코드로 옮겨 적었다. 처음에 승률을 계산할 때 100으로 해서 오류가 났는데, 다시 코드를 살펴보다 문득 한번이라도 패배하면 영원히 승률이 100이 될 수 없는 거 아닌가? 라는 생각이 들어서 99로 바꿨다. 

그냥 있는 그대로 작성하다보니 시간 복잡도가 O(N)이 되었는데 개선할 방법을 찾아보니 이분 탐색 알고리즘을 사용해

O(log N)으로 바꾸거나, 수학적인 접근을 통해 더욱 개선할 수 있다. 

 

 

---

다른 풀이

 

1. 이분 탐색 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        long all = scanner.nextLong();    // 전체 게임 횟수
        long wins = scanner.nextLong();   // 승리한 횟수
        scanner.close();

        long rate = (wins * 100) / all;  // 현재 승률 계산

        if (rate >= 99) {  // 승률이 99 이상이면 승률을 올릴 수 없으므로 -1 반환
            System.out.println(-1);
            return;
        }

        long left = 0;
        long right = all;
        long answer = -1;

        while (left <= right) {
            long mid = (left + right) / 2; // 중간 값을 승리 횟수로 가정
            long newRate = ((wins + mid) * 100) / (all + mid);

            if (newRate > rate) {  // 목표 승률에 도달한 경우
                answer = mid;
                right = mid - 1;   // 더 적은 승리 횟수로 목표를 달성할 수 있는지 확인
            } else {
                left = mid + 1;    // 더 많은 승리가 필요
            }
        }

        System.out.println(answer);
    }
}

 

left를 0, right를 all로 초기화 한 후, 중간값(mid)를 추가 승리 횟수로 가정하고 새로운 승률을 계산한 뒤에, 만약 새로운 승률이 기존 승률보다 높으면 mid에 값을 저장하고 right를 줄여 더 작은 승리 횟수로 목표 승률을 달성할 수 있는지 계산한다. 새로운 승률이 목표 승률에 도달하지 못한다면 ( 기존 승률보다 낮으면) left를 증가시킨다. 

 

 

 

아래가 기존 자연어를 그대로 해석한 코드고, 위에는 이진트리 방법으로 시간을 줄인 코드다. 

 

2. 수학적 접근

 

1. 목표승률 Z+1에 도달하기 위한 식은 다음과 같다.

2. 양 변에 (Y+N)을 곱해 정리

 

3. 이식을 다시 풀어 N에 대해 정리하고

 

4. N을 한쪽에 모은다.

5. 마지막으로 N에 대해 정리하면 다음과 같다.

나머지는 이식을 그대로 코드로 옮겨 적으면 끝이다.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        long all = scanner.nextLong();    // 전체 게임 횟수
        long wins = scanner.nextLong();   // 승리한 횟수
        scanner.close();

        long rate = (wins * 100) / all;  // 현재 승률 계산

        if (rate >= 99) { 
            System.out.println(-1);
            return;
        }

        // N을 계산하여 승률을 rate + 1로 올리기 위한 최소 추가 승리 횟수를 찾기
        long answer = ((rate + 1) * all - 100 * wins) / (100 - (rate + 1));
        
        // 나누어 떨어지지 않을 경우 올림 처리
        if (((rate + 1) * all - 100 * wins) % (100 - (rate + 1)) != 0) {
            answer++;
        }

        System.out.println(answer);
    }
}

 

 

결과는 아래에서부터 자연어, 이진트리, 수학적 접근 방법

 

 

시간이 같긴한데 수학적 접근 방법이 더 편한 것 같다. 종이와 펜만 있다면