백준 1300 풀이 (k번째 수, 이분 탐색)

이제 슬슬 알고리즘 풀때 음악을 들으면 안되겠다는 생각이 점점 들기 시작했다.....

그래서 오늘은 음악을 듣지 않고 천천히 집중해서 풀어보았다.

 

문제에서 주어지는 입력값이 굉장히 크다. 그래서 배열을 직접 만들어서 선언하며 풀게되면 메모리나 시간적인 측면에서 굉장히 손해를 볼수 있다.

따라서 어떻게 풀어야 할지 고민해보고 어떤 방식을 쓰면 좋을지 고민해 보았다.

우선 이분 탐색 문제이기 때문에 어떤 오름차순을 선택해서 풀어야할지 고민해보았다.

그 중에서 쓸만하다고 생각했던것은 행렬에 존재할 수 있는 수의 오름차순이었다.

예를 들어 3x3행렬이라면 1~9까지 나올수 있는 수이고, 4x4행렬이라면 1~16까지가 나올수 있는 수이다.

그럼 3x3행렬일경우

n = 3, k = 7

행렬은 [[1,2,3],[2,4,6],[3,6,9]]

l	m = (l+r)//2	r
1	5	9	m이 5라면 몇번째 정도일지 예상해보는것이다. 행렬을 1행부터 3행까지 몇개의 값이 5보다 작은지 확인하면 3+2+1 = 6개가 된다. 그럼 k값보다 작기 때문에 l값을 m+1로 바꿔준다.
6	7	9	m이 7일때 각 행을 비교하면 3+3+2 = 8개가 된다. 이러한 경우 k를 초과하기 때문에 r을 m-1로 바꿔준다.
6	6	6	m이 6일때 각 행을 비교하면 3+3+2=8이된다. 그러나 l과 r이 같기 때문에 최적값으로 생각되어 루프를 벗어난다. 그럼 실제로도 7번째 값은 6이된다.

이러한 방식으로 값을 찾아내면 된다. 단, n=3,k=8인 경우에는 7이하의 값도 8개, 6이하의 값도 8개로 중복되는 경우가 존재한다. 이러한 경우에는 l,r값을 잘 조절하여 움직이면 문제없이 루프를 돌 수 있다.

이러한 경우 7이 먼저 발견되기 때문에 나는 리스트에 저장하여 리스트중에 최저 값을 마지막에 출력하는 방식으로 코딩을 진행했다. 다른 풀이들도 확인해 봤으나 내 수준에서는 어려웠기 때문에 기존의 풀이가 어려운 사람들에게 내 풀이가 도움이 되었으면 좋겠다.  

n = int(input())
k = int(input())
l = 1
r = n*n
m = (l+r)//2
tmp = []
while l < r:
    # calc
    count = 0
    for i in range(1,n+1):
        if n*i <= m:
            count+= n
        else:
            count += m//i
    if count > k:
        r = m
    elif count < k:
        l = m + 1
    else:
        tmp.append(m)
        r = m
    m = (l+r)//2
if len(tmp) != 0:
    print(min(tmp))
else:
    print(m)