(파이썬) 백준 1300번 : K번째 수

백준 1300번 : 링크
문제를 이해해보자면, N x N 배열의 i행 j열의 들어있는 수는 i x j 라고 한다.
이 수들을 모두 1차원 배열에서 오름차순 정렬을 할 때,
1차원 배열의 K번째 수가 무엇인지 찾는 문제이다.

설계

꽤 까다로운 문제인 것 같다는 생각이 든다.
브루탈적인 접근(일일이 비교탐색) 은 당연히 시간초과일 것이고
DP로 구현하자니 점화식이 도저히 안보인다.

먼저, 임의의 수 Num을 배열과 비교하는 방법에 대해 생각했다.
i번째 행은 i의 배수들로 이뤄져있다. i x 1, i x 2,..., i x N
행의 특징은 확실히 알고 있으니, 일단 행 단위로 Num과 비교해보자.

Num을 특정 행과 비교한다면 어떤 정보를 얻을 수 있는가.
가장 먼저 떠오르는 것은 Num보다 작은 수가 몇 개 있는지 찾는 것이다.

만약 num이 i의 배수라면,
num을 i로 나눈 몫이 i번째 행에 존재하는 num보다 작거나 같은 수의 개수와 같다.
ex1) num = 14, i = 2 이면, 14 // 2 = 7이고 2, 4, 6, 8, 10, 12, 14 가능.
ex2) num = 9, i = 3 이면, 9 // 3 = 3이고 3, 6, 9 가능.

그렇다면 num이 i의 배수가 아니라면?
그래도 성립한다. 숫자를 몇 개 대입해보면 금방 알 수 있다.
ex3) num = 13, i = 2 이면, 13 // 2 = 6이고 2, 4, 6, 8, 10, 12 가능.
ex4) num = 11, i = 5 이면, 11 // 5 = 2이고 5, 10 가능.

하지만, 대충봐도 반례가 떠오른다. 바로 num // i 가 배열의 크기보다 큰 경우다.

가령, num = 14이고, i = 1이라면
num // i = 14이지만, 배열의 크기 N이 5 이면 14개가 될 수 없으니
결과는 5개가 될 것이다.

따라서 N보다 num // i가 클 때의 결과는 N이다.

모든 행에 대해서 연산을 반복하면
배열에서 num보다 작거나 같은 수의 개수를 구할 수 있게 되었다.

이제 num보다 작거나 같은 수가 K개인 num을 구하면 된다.

문제는 정확히 K번째 수를 구해야 하는데, 조건을
4만 하더라도 (2행 2열), (4행 1열), (1행 4열) 총 3번 등장한다.

그렇기 때문에 필요한 것이 매개변수 탐색이다.
매개변수 탐색까지 설명하려면 글이 너~~무 길어지니까 생략하고 핵심만 말하자면
이분탐색을 사용해서 조건을 만족하는 가장 작은(큰) 수를 찾는 과정이다.

이 문제에서 매개변수 탐색을 사용하면,
자기 자신보다 작거나 같은 수가 K개인 숫자중 가장 작은 수,
즉 K번째 수를 구할 수 있다.

구현

위에서 한참 떠들었던 num보다 작거나 같은 수를 구하는 과정부터 구현해보자.

1. 총 개수를 저장할 변수 count를 선언한다.
2. count에 각 행에 num보다 작거나 같은 수의 개수를 더한다.
   2 - 1.반복문으로 모든 행에 대해 num // i를 구해서 count에 더한다.
   2 - 2. num // i가 N(배열의 크기)보다 크다면 N을 count에 더한다.
3. count를 반환한다.

코드로는

# N x N배열에서 mid보다 작거나 같은 수의 개수를 반환하는 함수
def find_less(N,mid):
    count = 0
    for i in range(1,N + 1):
        tmp = mid // i
        # N보다 크다면 tmp를 N으로 수정해야 함
        if tmp > N : tmp = N
        count += tmp #tmp를 count에 더함
    return count

입력으로는 배열의 크기 N과 찾아야하는 K를 받는다.

N = int(input())
K = int(input())

이제 매개변수 탐색을 구현해보자.

이분탐색에 사용할 양 끝을 left와 right로 하면
left와 right의 초기값은 0과 N x N 이다.

#가능한 수의 범위는 1부터 N의 제곱
left = 1
right = N ** 2

반복문의 구성

0. mid 는 left와 right의 평균
1. find_less(mid) 를 구하고
2. 이 값이 K보다 크거나 같다면 : answer를 mid로 갱신 그리고 right를 mid - 1로 갱신
3. 이 값이 K보다 작다면 : left를 mid - 1로 갱신

이 과정을 left가 right보다 작거나 같을 동안 반복하면
자연스럽게 find_less(answer) = K 를 만족하는 answer를 구할 수 있다.

코드가 이해 안갈수도 있는데
매개변수 탐색은 다양한 문제들을 보고 해결방법을 찾아보면서
익숙해지는 것이 빠른 것 같다. (글로 설명하기 너무 힘들다..죄송..)

while left <= right:
    mid = (left + right) // 2
    tmp = find_less(N,mid)
    
    #right를 수정하기 때문에 mid는 작아짐
    #별도의 탈출문없이 계속해서 반복문이 돌아가게 되면
    #mid는 조건을 만족하는 가장 작은 수로 맞춰지게 됨
    if tmp >= K :
        #결과갱신
        ans = mid
        right = mid - 1
    else :
        left = mid + 1

print(ans)

전체코드

# N x N배열에서 mid보다 작은 수의 개수를 반환하는 함수
def find_less(N,mid):
    count = 0
    for i in range(1,N + 1):
        tmp = mid // i
        # N보다 크다면 tmp를 N으로 수정해야 함
        if tmp > N : tmp = N
        count += tmp #tmp를 count에 더함
    return count

N = int(input())
K = int(input())

#가능한 수의 범위는 1부터 N의 제곱
left = 1
right = N ** 2

#이분탐색
while left <= right:
    mid = (left + right) // 2
    tmp = find_less(N,mid)
    
    #right를 수정하기 때문에 mid는 작아짐
    #별도의 탈출문없이 계속해서 반복문이 돌아가게 되면
    #mid는 조건을 만족하는 가장 작은 수로 맞춰지게 됨
    if tmp >= K :
        #결과갱신
        ans = mid
        right = mid - 1
    else :
        left = mid + 1

print(ans)

후기

1300번 해설을 해봤는데.. 설명하기 참 어렵네요..
이진탐색과 매개변수 탐색에 대해 잘 모른다면 해결하기 어려울 것 같습니다.
(해설을 봐도 이해하기 쉽지 않을듯)

누구나 이해할 수 있는 해설을 작성하고 싶었는데
한계가 있는 것 같습니다...

피드백과 질문은 언제나 환영합니다.