백준 1300-K번째수

알고리즘 분류: 파라메트릭 서치, 이분 탐색

 

설명하기 전에, 파라메트릭 서치(매개 변수 탐색)에 대해 알아볼 필요가 있다.

파라메트릭 서치는 "...한 값을 찾으라" 하는 문제를 "이 값은 ...인가?" 하는 예/아니오를 판별하는 간단한 문제로 바꾸어서 탐색하는 것이다. 그렇다면 파라메트릭 서치는 이분 탐색과 연계되기 매우 좋은 조건을 가지고 있다.

이 문제에서도 "...한 값을 찾으라" 형태의 문제 형식을 따르고 있다. 따라서 이 문제를 풀기 위해 예/아니오를 판별하는 문제로 바꾸는 것이 중요하다.

 

다음 아이디어를 생각해보자.

글씨가 매우 안 좋아 보인다. ㅋㅋ

어떤 리스트를 오름차순으로 "정렬"한다는 것은 크기가 작은 순서부터 큰 순서대로 배열한다는 것이다.

그렇다면 정렬 리스트에서 제일 마지막 값은 최댓값이고 제일 첫 번째 값은 최솟값일 것이다.

최댓값은 자신보다 작거나 같은 수의 개수가 바로 배열의 크기가 될 것이고, 최솟값은 자신보다 작거나 같은 수의 개수가 곧 자신 하나 밖에 없게 된다.

그렇다면 문제에서 바라는 B[k]를 정리해보면, B[k] = (어떤 수)에 대하여 (어떤 수)보다 작거나 같은 수의 개수가 k개가 되지 않을까?

 

그렇다면 곧바로 예/아니오를 판별하는 문제가 나올 수 있게 된다.

어떤 a에 대하여 a보다 작거나 같은 수의 개수가 k보다 많은가?

이 문제를 함수로 생각한다면 곧 1과 0으로만 구분되는 논리함수가 될 것이다.

저번 https://lcj207.tistory.com/11 글에서 볼 수 있듯이, 이분탐색은 어떤 상황에서 용이하게 쓸 수 있냐면 

무슨 무슨 조건을 만족하는데, 그것의 최대/최소를 구하라 형식의 문제를 풀 때 용이하게 사용할 수 있다.

 

만일 a보다 작거나 같은 수의 개수를 기준으로 이분 탐색을 수행한다면, k보다 많은 것이 참이면 상한을 줄여 탐색을 시행한다. 만약 k보다 적다면(즉 위 함수의 리턴값이 0이라면) 하한을 늘려 탐색을 시행한다면 언젠가 k의 수에 도달하게 될 것이다. 

이때 수렴값을 B[k] = A라하면 A는 곧 문제에서 구하는 정답이 될 것이다.

 

그러면 코드를 짜보자

n = int(input())
k = int(input())
def para(a):
    cont = 0
    for i in range(1, n+1):
        cont += min(a//i, n)
    return k <= cont
low = 1
hi = n**2
for i in range(200):
    mid = (low+hi)//2
    if para(mid):
        hi = mid
    else:
        low = mid+1
print(mid)

매우 사소한 부분이지만, low = mid+1 부분 때문에 20분이나 더 고민했었다.

처음 입력 예제 

3

7

에서 계속 나오라는 6이라는 안나오고 5가 나왔었다.

이건... 이분 탐색에 대한 내 지식의 문제였던 것이었다.

그래서 무작정 인터넷에

이분탐색을 검색하여 세 가지 사실을 알았다.

lower bound와 upper bound이 두 가지의 방법이 이분 탐색에 존재한다.

현재 사용했던 방법은 lower bound로, 겹치는 값이 존재하여 가장 작은 값을 도출할 때 사용한다.

 

그리고 else 부분에서 low(시작부분)을 mid+1로 하는 것도 알았다!!

 

그렇다면 나는 왜 그토록 많은 이분탐색 문제를 풀면서 이와 같은 문제점을 눈치채지 못했을까?

그것은 값이 겹치지 않아서 그랬던 것 같다. 앞으로 이 사실을 계속 되뇌면서 문제를 풀어야겠다...

 

역시 저는 코딩 새싹입니다 ㅠ