크래프톤 정글 8기 - 16일차 TIL (이분탐색 문제풀이)
TIL - 2025.03.26 (수요일)
📝 오늘 배운 것 (이분 탐색 문제 풀이)
백준 1072번 게임
풀이 코드
x, y = map(int, input().split())
start_rate = (y * 100) // x
if x == y:
print(-1)
elif start_rate >= 99:
if ((y + 10**9) * 100) // (x + 10**9) <= start_rate:
print(-1)
else:
start, end = 1, 10 ** 9
while start <= end:
mid = (start + end) // 2
new_z = ((y + mid) * 100) // (x + mid)
if new_z > start_rate:
end = mid - 1
else:
start = mid + 1
print(start)풀이 소개
이 문제는 앞으로 모든 게임이 이긴다는 가정아래 자신의 승률이 변하는 가장 최소 게임 판수를 구하는 것이었다.
승률의 경우 소수점은 버리기 때문에 예시처럼 80%가 시작 승률이었다면 81%가 되는 최소 게임 횟수를 구하는 것이었다.
이분탐색을 이용해 1 부터 x의 최대 범위인 1,000,000,000번 까지 게임 횟수를 이분탐색으로 줄여가며 최소 게임 횟수를 찾아내는 작업을 진행했다.
이 때 처음에는 당연히 틀렸다는 결과를 얻게 되었다. 몇 가지 경우의 수를 놓친 것 이었다.
- 만약 x와 y 가 같은 값이라 승률이 100%인 경우에는 바로 -1을 출력해야 한다.
- 시작 승률이 이미 99%로 시작했다면 아무리 많은 게임을 해도 100%의 승률이 될 수 없을 것이다. 그렇기 때문에 이런 경우에 대해서고 -1을 출력해야 했다.
그나마 이 문제는 입출력 예제가 많이 주어졌기 때문에 문제를 찾을 수 있었다.
백준 1300번 K번째 수
풀이 코드
n, k = int(input()), int(input())
start, end = 1, k
while start <= end:
mid = (start + end) // 2
temp = 0
for i in range(1, n + 1):
temp += min(mid // i, n)
if temp >= k:
answer = mid
end = mid - 1
else:
start = mid + 1
print(answer)풀이 소개
이 문제는 초기 개념을 잡는 것에 매우 애를 먹고 결국 우리의 인공지능 선생님을 찾아갔던 문제였다. 처음에 문제를 봤을 때 일단 입력값의 크기나 여러 요소를 봤을 때 배열에 들어가는 값들을 직접 계산하는 것은 무조건 문제가 있는 방법이라 생각되어 수학적인 접근을 하려고 했으나 쉽게 해법이 생각나지 않았다.
for i in range(1, n + 1):
temp += min(mid // i, n)이 부분의 min(mid // i, n)의 이해를 위해 한참을 끄적이며 왜 이렇게 되는지 고민했던 부분이었다. 이런 코드를 사용한 이유는 각 행에서 mid 이하인 값의 개수를 효율적으로 계산하기 위한 방법이기 때문이다.
예를 들어 n이 20이고 mid 가 30이라고 한다면
- i = 1일 때: mid//i = 30//1 = 30이다. 하지만 n=20이기 때문에 min(30, 20) = 20이다.
- 즉, 1행에서 20개의 값이 30 이하라는 것이다.
- i = 2일 때: mid//i = 30//2 = 15이다. min(15,20) = 15이다.
- 즉, 2행에서 15개의 값이 30 이하다.
- i = 3일 때: mid//i = 30//3 = 10, min(10,20) = 10
- 즉, 3행에서 10개의 값이 30 이하이다.
이런 식으로 각 행마다 mid값 이하인 값의 개수를 계산하고 이 개수들을 모두 더하면 2차원 배열 A를 1차원 배열 B로 변환한 수 정렬했을 때, mid 이하인 값의 총 개수가 된다.
그리고 이 값을 찾기 위해 이분탐색을 진행한다.
🧐 느낀 점
문제의 풀이방법을 찾는 것도 중요하고 세부적인 조건들을 파악할 수 있는 능력도 중요하다는 것을 알게 되었다. K번 째 수와 같은 계산 방법을 생각하는 것은 매우 어려운 것 같다...