99클럽 코테 스터디 1일차 TIL

백준 - 1072번

 

처음 문제를 봤을 때, 눈에 띄었던 부분들이 있다.

• 이제 형택이는 앞으로의 모든 게임에서 지지 않는다.
• 게임 기록
• 만약 Z가 절대 변하지 않는다면 -1을 출력한다.

키워드 힌트로 이분탐색이 주어졌지만 처음에는 알고리즘을 적용하지 않고 시도해 보았다.

import java.util.Scanner;

public class Main {

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

        double x = sc.nextDouble();
        double y = sc.nextDouble();
        int z = (int) ((y / x) * 100);

        int count = 0;
        if (x != y) {
            for (double i = y + 1; i <= x + 1; i++) {
                x++;

                int rate = (int) ((i / x) * 100);

                count++;

                if (rate != z) {
                    break;
                }
            }
        } else {
            count = -1;
        }

        System.out.println(count);
        sc.close();
    }
}

위 코드로 예제에 나와있는 케이스들을 입력했을 때 정상적으로 출력되어 제출해 봤지만 틀렸다.

 

게임이 진행되면 게임 횟수와 이긴 횟수 모두 1씩 증가한다.

반복문을 돌 때마다 승률을 계산하고, 새로 계산한 승률과 기존 승률이 다른 경우 반복문을 종료하도록 구현했다.

그리고 기존 게임 횟수와 이긴 횟수가 같을 때만 -1이 출력되도록 했다.

 

여기서 문제는 동일한 승률이 반복된다면 무한 루프에 빠지게 된다는 것이다.

만약 기존 승률이 99%라면 어떻게 될까.

반복문이 끝나지 않아 결과가 출력되지 않는다.

100%가 되려면 게임 횟수와 이긴 횟수가 동일해야 하는데, 둘 다 하나씩 증가하기 때문에 성립될 수 없다.

---

더 눈여겨봐야 했던 것은 문제의 '제한' 부분이다.

반복문을 10억 번 돌게 하는 것도 굉장히 비효율적이지만

입력 값이 10억이나 9억 999.. 라면 어떻게 구현해야 할 지도 막막하다. 

 

여기서 알고리즘을 적용해 보자.

이분탐색

• 정렬되어 있는 데이터에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터를 찾는다.
• 변수로 start, mid, end / left mid right 등을 사용

문제에 어떻게 적용해 볼 수 있을까.

• 제한된 수 안에서 중간 지점의 숫자 mid 선택
• 게임을 mid번 진행했을 때의 승률과 기존 승률 비교
• 승률이 같은 경우, mid 보다 큰 수의 범위를 탐색하여 다시 비교 
• 승률이 다른 경우, mid 보다 작은 수의 범위를 탐색하여 다시 비교 

위 과정을 반복하여 결괏값을 찾는다.

import java.util.Scanner;

public class Main {

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

        int x = sc.nextInt();
        int y = sc.nextInt();
        int z = getRate(x, y);

        int result = -1;
        int start = 0;
        int end = 1_000_000_000;
        while (start <= end) {
            int mid = (start + end) / 2;

            if (getRate(x + mid, y + mid) != z) {
                result = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        System.out.println(result);
        sc.close();
    }

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

100 99 값이 주어진 경우,  99%로 -1 이 출력되어야 한다.

기존에는 10억 번을 전부 돌았지만 알고리즘 적용으로 반복 횟수가 약 30번으로 줄었다.

---

코테를 많이 풀어보진 않았지만 그중에서도 알고리즘을 적용해서 풀어본 문제는 없었던 것 같다.

'알고리즘은 어렵다'라는 인식이 강해 항상 기초적인 문제만 풀어왔다.

 

코테스터디를 통해 그 인식을 조금이라도 깨고자 한다.

 

백준 1072번 게임

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