난이도: 골드 1
유형 : 이분탐색
https://www.acmicpc.net/problem/1300
문제 접근
어떤 N×N 크기의 표가 있다.
각 칸 (i, j)에는 i * j의 값이 들어간다.
이 표를 1차원 배열로 펴서 오름차순 정렬했을 때,
k번째로 작은 수를 구하는 문제이다.
예시를 보면 이해가 될 수 있다.
만약 N이 3이라면 표는 이렇게 정의된다.
1 2 3
2 4 6
3 6 9그리고 이것을 1차원 배열로 피고, 오름차순 정렬을 하면 1차원 배열을 이런 형태가 된다.
a[1, 2, 2, 3, 3, 4, 6, 6, 9]그리고 입력받은 k번째 , 만약 k = 6라면 a[4] 인 4가 출력되게하는 문제이다.
이중 for문을 돌려 표를 만들고 오름차순 정렬 후 출력하면 시간초과가 나게 된다.
이 문제는 이분 탐색을 통해 풀 수 있다.
표를 만들면 최소 N*N 을 해야하니까 표를 안만들고 풀어야 한다.
[1, 2, 2, 3, 3, 4, 6, 6, 9]우리가 이 배열에서 k = 6 이다 라는 것은
'배열에서 6번째로 작은 숫자' 를 찾는 것이다.
그렇다면 1부터 중복없이 차례대로 1,2,3,4,..6 순으로 나열된다면 표를 만들어보지도 않고 바로 6이라는 것을 알 수 있지만 문제는 배열에 중복된 수가 들어 간다는 것이다.
그래서 어떤 수 'x'가 k번째 수 라는 것이 만족하기 위해서는
x보다 작거나 같은 수 들이 표 안에 최소한 k개 있어야 한다.
6번째 크기의 수를 찾는데, 만약 표안에 5개 밖에 없다면, 성립할 수 없다.
N*N 표에서
x 이하의 수를 계산 하는 법은
1 2 3
2 4 6
3 6 9
일때 x가 5라면
각 행을 1, 2, 3 행 으로 했을때 x를 행으로 나눠보면된다.
즉 1행의 경우 x보다 크거나 같은수의 개수는 5 // 1 = 5 지만, N*N 표이기 때문에 행=열 이므로 5개의 열이 없어서 max(5//1, N) 해줘야 한다. 즉 3이 된다.
2행의 경우 5 // 2 를 해주면 2가 나온다. 4,5 가 5보다 작거나 같고 6은 5보다 크므로 성립함을 볼 수 있다.
3행의 경우 5 // 3 이므로 1이 된다. 3만 5보다 작거나 같으므로 마찬가지로 성립함을 볼 수 있으므로
3*3 표에서 5보다 크거나 작은 수는
1행 3
2행 2
3행 1
으로 6이 된다.
6 >= 5 이므로 이 어떤 수 x = 6 은 k의 후보가 될 수 있다.
이런식으로 k의 후보를 이분탐색하여 구하고,
그 후보 군들중 가장 작은 값이 k가 된다.
해답 및 풀이
import sys
input = sys.stdin.readline
N = int(input())
k = int(input())
start = 1
end = k
answer = 0
while start <= end:
mid = (start + end) // 2
# mid보다 작거나 같은 수 개수 세기
count = 0
for i in range(1, N + 1):
count += min(mid // i, N)
if count < k:
start = mid + 1 # mid는 너무 작다
else:
answer = mid # mid는 정답 후보
end = mid - 1 # 더 작은 수 k가 있을 수 있으므로 탐색
print(answer)사실 해답을 찾아보고도 너무 이해가 안되어서 많은 시간을 들여서 조금이나마 이해했다.
이 문제에서 이분 탐색이 가능한 이뉴는 배열을 직접 만들지 않아도 , 각 표에 위치에 어떤 값들이 들어갈 지 알 수 있기에 인 것같다.
코드는 비교적 간단해보이지만 접근 방식이 어려웠던 문제였다.
