[TIL] 99클럽 코테 스터디 1일차 TIL - 이진탐색 : 백준 1072 게임 문제 풀이 with python

Today's keyword : 이진탐색 

이진탐색이란? 

  정렬된 배열에서 특정 값을 찾기 위해 반으로 나누면서 탐색해 나가는 알고리즘입니다. 이 방법은 배열이 정렬되어 있어야 사용 가능합니다. 

이진탐색 작동원리 

1. 초기 설정 : 배열의 시작과 끝 인덱스를 설정 

2. 중간 인덱스 계산 : 시작 인덱스와 중간 인덱스 계산 

3. 비교 

• 중간 인덱스의 값이 찾고자 하는 값과 같으면 탐색 종료 
• 중간 인덱스의 값이 찾고자 하는 값보다 크면, 끝 인덱스를 중간 인덱스 - 1로 설정하여 왼쪽 절반을 탐색
• 중간 인덱스의 값이 찾고자 하는 값보다 작으면, 시작 인덱스를 중간 인덱스 + 1로 설정하여 오른쪽 절반을 탐색

4. 반복 : 절반으로 나누면서 시작 인덱스가 끝 인덱스 초과할 때까지 반복 

문제설명

 

형택이가 게임을 몇 번 더 해야 승률이 변하는지를 찾는 것으로, 주어진 입력은 두 개의 정수 X (총 게임 수)와 Y (이긴 게임 수)입니다. 승률 Z는 𝑌를 𝑋로 나눈 후 100을 곱하여 계산합니다. 이때 소수점은 버립니다. 

이 문제에서 이진 탐색이 필요한 이유는 예시 문제와 범위를 보면 탐색해야 할 범위가 큽니다. 단순히 반복문으로 순차적으로 탐색할 경우, 시간초과에 걸리게 됩니다.  이진 탐색을 사용하면 탐색 범위를 반으로 줄여가며 효율적으로 답을 찾을 수 있습니다.

 

또한, 승률이 변하는 조건은 추가 게임 수에 따라 달라집니다. 즉, 추가 게임 수가 증가함에 따라 승률이 어떻게 변하는지를 확인해야 합니다. 이진 탐색을 통해 중간값을 설정하고, 그 중간값에서 승률이 변하는지를 확인함으로써, 승률이 변하는 최소 게임 수를 찾을 수 있습니다.

이 문제는 승률이 증가하는 조건이 정렬된 상태로 나타납니다. 즉, 추가 게임 수가 증가할수록 승률도 증가하는 경향이 있습니다. 이진 탐색은 이러한 정렬된 상태에서 매우 효과적입니다.시간 복잡도는 O(log N)입니다. 

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

 

문제풀이

X, Y = map(int, input().split())
current_win_rate = (Y * 100) // X  # 현재 승률

# 승률이 변하지 않는 경우
if current_win_rate >= 99:
    print(-1)
    exit()

# 이진 탐색을 위한 초기 설정
min_games = 0
max_games = 10**9  # 충분히 큰 수로 설정
result = -1

while min_games <= max_games:
    mid_games = (min_games + max_games) // 2
    new_wins = Y + mid_games
    new_games = X + mid_games
    new_win_rate = (new_wins * 100) // new_games

    if new_win_rate > current_win_rate:
        result = mid_games  # 승률이 변하는 경우
        max_games = mid_games - 1  # 더 적은 게임 수를 시도
    else:
        min_games = mid_games + 1  # 더 많은 게임 수를 시도

print(result)

1. 현재 승률 계산: `current_win_rate`를 계산합니다. 이때 소수점은 버리기 위해 몫을 계산합니다.

2. 승률이 변하지 않는 경우 처리: 현재 승률이 99% 이상인 경우, 승률이 변하지 않으므로 -1을 출력합니다.

3. 이진 탐색 수행:

• 최소 게임 수(min_games)와 최대 게임 수(max_games)를 설정합니다.
• 중간 게임 수(mid_games)를 계산하여 새로운 승리 수와 게임 수를 업데이트합니다.
• 새로운 승률이 현재 승률보다 크면, 승률이 변하는 경우이므로 결과(result)를 업데이트하고 더 적은 게임 수를 시도합니다.
• 그렇지 않으면 더 많은 게임 수를 시도합니다.

3. 결과 출력: 최종적으로 승률이 변하기 위해 필요한 최소 게임 수를 출력합니다.

 

오늘의 회고 

이진탐색의 기본적인 문제를 풀었다. 탐색 범위가 넓은 정렬된 배열에서 이진탐색은 효과적이며, 작동원리는 탐색 시작점과 끝점을 초기 설정한 후 조건에 맞을 때까지 (여기서는 승률 변화) 중간 인덱스를 업데이트 하는 방식으로 진행한다.