알고리즘 스터디 - 백준 1300번 : K 번째 수

문제 해석

• 배열 A = NxN 행렬, A[i][j] = ixj
• 일차원 배열 B에 집어넣으면서 NxN 크기가 됨
• B를 오름차순으로 정렬하면 B[k]를 구하는 것임

어떤 알고리즘을 사용해야 할까?

3 <- N
7 <- k

# A의 행렬 모습은 아래와 같다. 
# i != j 이면 A[i][j] = A[j][i] 2개씩 들어감
# i == j 이면 1개만 들어감
for i in range(0, N):
    for j in range(i, N):
[
    [1, 2, 3],
    [2, 4, 6],
    [3, 6, 9]
]

이런 형식으로 집어넣고 bisect를 사용하니 시간초과가 나왔다. 다른 방식을 사용해보자. 여기서 k = 7이고 B[7]인데 "전체 숫자 중에서 7에 해당되는 숫자보다 작거나 같은 숫자의 개수가 7개보다 작으면 안된다" 라는 가정으로 보면 그 숫자가 6이라면 전체 8개가 있다.

[
    [1, 2, 3], <- 3개
    [2, 4, 6], <- 3개
    [3, 6, 9]  <- 2개
]

만약 3이라면?

[
    [1, 2, 3], <- 3개
    [2, 4, 6], <- 1개
    [3, 6, 9]  <- 1개
]

공식 = min(타겟 숫자 // i, N)임을 알 수 있다.

알고리즘 코드

N = int(input())
k = int(input())

left, right = 1, k
mid = 0
answer = 0

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

print(answer)