[알고리즘] 백준 1300 - K번째 수

1. 문제 

k 번째 수

2. 접근

1. 처음에는 a에 대한 2차원 배열을 만들어서 2차원 배열에 값들을 넣어주고, b리스트안에 2차원 배열을 sum(a, [] ) 라는 메소드로 1차원 배열을 만들어서 해결하려고 하니 메모리 초과가 나왔다.

2. 그래서 이분 탐색을 사용하였다.

3. 가장 중요한 부분이 임의의 수 a보다 작거나 같은 개수를 구하여야 하고, 각 행은 구구단 처럼 나타나기에 ( a / 행번호 ) 가 그 행에서 구하고자 하는 값이 된다, 단 ( a / 행번호 ) 가 n보다 크면 그 값은 n임을 알아야 한다

 

 

3. 풀이

import sys
input = sys.stdin.readline

n = int(input())
k = int(input())

a = [[1] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        a[i][j] = (i+1)*(j+1)


b = sum(a, [])

b.sort()

print(b[k])

처음 메모리 초과 나온 코드

 

import sys
input = sys.stdin.readline

n = int(input())
k = int(input())

start = 1
end = k
res = 0

while start <= end:
    mid = (start+end) // 2
    target = 0

    for i in range(1, n+1):
        target += min(n, mid//i)
    if target < k:
        start = mid + 1
    else:
        res = mid
        end = mid - 1

print(res)