백준 1300 - K번째 수 (파이썬)
글 작성자: pental
https://www.acmicpc.net/problem/1300
풀이
- 문제 조건
- N×N 크기의 배열 A가 있음.
- A[i][j] = i × j 로 채워져 있음.
- 이 배열을 일차원 배열로 변환하고 정렬했을 때, K번째로 작은 수를 찾아야 함.
- mid 값 기준으로 몇 개의 원소가 작은지 확인
- mid 값보다 작거나 같은 원소 개수를 구해 count 값으로 활용.
- 특정 수 X보다 작은 원소의 개수를 구하는 방법
- A[i][j] = i * j 이므로 i번째 행에서 X 이하의 수 개수 = min(N, (X - 1) // i)
- 모든 i (1~N)에 대해 누적하여 개수를 세면 된다.
- K와 비교하여 mid 조정
- count < K 이면 mid가 너무 작다는 뜻이므로 low를 증가.
- count >= K 이면 mid가 충분히 크므로 high를 줄임.
- 시간 복잡도 분석
- 이분 탐색의 탐색 범위: 1 ~ N*N → O(log(N^2)) = O(2 log N) = O(log N)
- 카운트 계산: O(N)
- 총 시간 복잡도: O(N log N)
코드
# 백준 1300 - K번째 수
# 분류 : 이분 탐색
N = int(input())
K = int(input())
low = 1
high = N * N
answer = -1
while low <= high :
mid = (low + high) // 2
count = 0
for i in range(1, N + 1) :
# i, 2 * i, 3 *i, ..., N * i
count += min(N, (mid - 1) // i)
if count < K :
answer = mid
low = mid + 1
else :
high = mid - 1
print(answer)
'Programming > 백준' 카테고리의 다른 글
백준 17952 - 과제는 끝나지 않아! (파이썬) (0) | 2025.03.07 |
---|---|
백준 19598 - 최소 회의실 개수 (파이썬) (0) | 2025.03.06 |
백준 1303 - 전쟁 - 전투 (파이썬) (0) | 2025.03.06 |
백준 14719 - 빗물 (파이썬) (0) | 2025.03.05 |
백준 17086 - 아기 상어 2 (파이썬) (0) | 2025.03.04 |
댓글
이 글 공유하기
다른 글
-
백준 17952 - 과제는 끝나지 않아! (파이썬)
백준 17952 - 과제는 끝나지 않아! (파이썬)
2025.03.07 -
백준 19598 - 최소 회의실 개수 (파이썬)
백준 19598 - 최소 회의실 개수 (파이썬)
2025.03.06 -
백준 1303 - 전쟁 - 전투 (파이썬)
백준 1303 - 전쟁 - 전투 (파이썬)
2025.03.06 -
백준 14719 - 빗물 (파이썬)
백준 14719 - 빗물 (파이썬)
2025.03.05