99클럽 코테 스터디 1일차 TIL - 백준[1072]

---

문제 풀이

오늘의 문제 - 백준1072.게임

나의 풀이

import java.util.*;
import java.io.*;

public class Main {
    public static void solution() throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine()," ");

		int x = Integer.parseInt(stk.nextToken());
		int y = Integer.parseInt(stk.nextToken());
        int z = (int) ((long) y * 100 / x);
        int answer = -1;
        int left = 0;
        int right = (int) 1e9;
        
        while (left <= right) { // left가 right를 넘어서면 종료
            int mid = (left + right) / 2;
            int newRate = (int) ((long) (y + mid) * 100 / (x + mid));
            if (newRate != z) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(answer);
    }

    public static void main(String[] args) throws IOException {
        solution();
    }
}

해결과정

• 게임 count(x,y) 를 하나씩 늘려가며, 승률(z)이 변하는지 일일이 체크하였다.
• 문제발생 : 시간 초과
• 찾아보니 이분탐색을 활용해야 한다는 것을 알게되었다.
• 이분탐색의 이론과 예시를 확인하고 다시 적용

---

오늘 배운 점

이분 탐색 / 이진 탐색 (Binary Search)

• 이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
• 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
• 변수 3개(시작, 중간, 끝)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.

이분 탐색 방법

1. 처음 범위는 인덱스 0부터 끝까지이다. 이 때 중간 인덱스를 mid로 한다.

2. mid의 값와 찾는 원소를 비교한다.
   2-1) 찾는 원소와 mid의 값이 같다면 탐색 종료한다.
   2-2) mid의 값 < 찾는 원소 일 때 left는 mid + 1로 하여 2)를 다시 반복한다.
   2-3) mid의 값 > 찾는 원소 일 때 right는 mid - 1 로 하여 2)를 다시 반복한다.

3. 만약 right > left가 된다면 해당 배열에 찾는 원소가 없는 것이다.

구현 예시(java) - 반복문 구현

public static boolean BSearch(int[] arr, int n) {
	int left = 0;
	int right = arr.length - 1;
	int mid;

	while (left <= right) {
		mid = (left + right) / 2;
		if (arr[mid] < n) left = mid + 1;
		else if (arr[mid] > n) right = mid - 1;
		else return true;
	}
	return false;
}