[백준 1300] K번째 수 (python)

https://www.acmicpc.net/problem/1300

1300번: K번째 수

K번째 수 문제

이분탐색을 이용하여 오름차순으로 정렬했을때의 K번째 수를 구하는 문제

100% 내 생각으로 풀었는가?
→ X

다른 사람의 코드를 계속해서 보면서도 한참이 지나서야 겨우 이해하고 해결한 문제

내가 푼 정답코드

import sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
start = 1
end = K

while start <= end:
    mid = (start + end) // 2
    cnt = 0
    # ex) N*N에서 20보다 작거나 같은 수는
    # 1행 기준 1~ 20 -> 20//1 개
    # 2행 기준 2,4,6,8... -> 20//2 개
    # 3행 기준 3,6,9,12... -> 20//3 개
    # 4행 기준 4,8,12,16,20... -> 20//4개
    # N행 기준 N,N*2,N*3... -> 20//N개!
    # 이중 찾는값//i가 N보다 큰 경우가 존재하므로 최대 N까지만 갖게 설정
    for i in range(1, N+1):
        cnt += min(mid//i, N)
    if cnt >= K:
        result = mid
        end = mid - 1
    else:
        start = mid + 1
print(result)

코드 답 자체는 굉장히 간단하지만, 2차원 배열을 이분탐색으로 어떻게 풀지?에서 굉장히 접근 난이도가 높았고, 이분탐색과 약간의 점화식을 생각해야 겨우 해결할 수 있는 문제이다.

반응형

N*N인 배열에서 특정 수 보다 작거나 같은 수를 찾는다고 생각해보자.

N을 설명을 위해 20으로 잡았고 설명은 다음과 같다

1행을 보면 1~20까지 20개

2행을 보면 1~20까지 10개

3행을 보면 1~20까지 6개

...

20행을 보면 1~20까지 1개

위와 같은 형태인 것을 볼 수 있다 즉 첫행부터 20//1개, 20//2개, 20//3개 ... 20//20개 만큼이 20보다 작다는 것을 확인할 수 있다. 다만 이중 찾는값//i가 N보다 큰 경우가 존재 할 수도 있기 때문에 최대 N까지만 갖게 설정을 해줄 필요가 있다.

이 말은 즉 위 예시는 N을 20으로 잡았지만, N이 만약 10일 경우  찾는값이 20인 지금 20//1의 경우 20이지만, 실제로 N은 10개 까지밖에 존재하지 않으니 20//1과 N중에 더 작은 값을 구해주는 것이다.

따라서 이를 식으로 표현한 것이 min(mid//i,N)인 것이다.

---

느낀점

굉장히 접근이 어려웠던 문제였다. 무엇보다 1차원 리스트에서만 사용하던 이분탐색을 2차원 리스트로 확장하니 어떻게 접근해야할지 감을 잡기 어려웠다. 그래서 다른 사람들의 코드를 참고했고, 이해하는데 한참이 걸렸다. 위 해설과 같은 부분이 이 문제 해결의 제일 핵심인 부분이기 때문에 저것만 알아내면 바로 답을 맞출 수 있는 문제인데, 그 생각에 도달하는게 굉장히 어려웠다.

아직 부족함을 많이 느꼈고, 좀 더 다양한 방식으로 접근하는 시도를 해볼 필요가 있음을 느낀 문제였다.