1300.md

Index

• 권준혁
• 안지완
• 오효근
• 조은학

---

K번째 수

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다.

출력

B[k]를 출력한다.

예제

입력 1

3
7

출력 1

6

---

권준혁

접근법 (생각의 흐름 설명)

상세한 해설

회고

Solution

---

안지완

접근법 (생각의 흐름 설명)

상세한 해설

회고

Solution

---

오효근

접근법 (생각의 흐름 설명)

당연히 brute-force로 풀리지 않을 것이므로 이분 탐색으로 접근했다.

상세한 해설

k를 끝 점으로 하고 tmp에 mid // i 값을 더해주어 k보다 작은 수를 셀 수 있다. 시간 복잡도는 $O(N\log{k})$이다.

회고

이분 탐색은 너무 어렵다.. ㅜ

Solution

import sys

read = sys.stdin.readline

if __name__ == "__main__":
    N = int(read())
    k = int(read())

    """
    # A = [[(i + 1) * (j + 1) for j in range(N)] for i in range(N)]
    A = [(i + 1) * (j + 1) for j in range(N) for i in range(N)]
    B = sorted(A)
    print(B[k])
    """

    left, right = 1, k
    while left <= right:
        mid = (left + right) // 2
        tmp = 0
        for i in range(1, N + 1):
            tmp += min(mid // i, N)
        if tmp >= k:
            res = mid
            right = mid - 1
        else:
            left = mid + 1
    print(res)

---

조은학

접근법 (생각의 흐름 설명)

• 문제 이해가 제일 어려웠다.
• 이분탐색이라는 것을 생각하는게 어려운 것 같다.

상세한 해설

• 문제가 어려워서 해설을 보았는데 조금 당황스러웠다...
• 이분탐색으로 풀면 된다...이게 왜 이분탐색인지 생각하기까지가 어려운 것 같다.
• 2차원 배열에서 이분탐색하는 과정이 너무 어려운것 같다..

회고

해설보고 어이가 없었다.

Solution

N, K = int(input()), int(input())
start, end = 1, K

while start <= end:
    mid = (start + end) // 2
    
    tmp = 0
    for i in range(1, N+1):
        tmp += min(mid//i, N) 
    
    if tmp >= K: 
        answer = mid
        end = mid - 1
    else:
        start = mid + 1
print(answer)