[백준] 1300번 K번째 수 (Python 파이썬)

www.acmicpc.net/problem/1300

1300번: K번째 수

문제 설명

이 문제에서 A라는 배열의 각 칸에는 다음과 같이 자기 인덱스의 곱을 담고있다. ( 즉 N[2][3] = 2*3 )

 

1	2	3
2	4	6
3	6	9

이러한 배열을 B라는 1차원 배열에 오름차순으로 나타내었을 때, k번째 인덱스에는 어떤 수가 있는지를 출력하는 문제이다.

---

풀이 과정

 

처음에는 N*N크기의 1차원 배열을 만들어 for문을 이용해 1*1부터 N*N까지의 수를 모두 넣어주고 정렬을 한 후에

그 배열의 k번째 수를 출력하도록 설계하였다.

하지만 문제에서 N은 10^5보다 작거나 같은 자연수이기 때문에 N*N크기의 배열을 만들려면 10^10만큼의 굉장히 많은 메모리가 필요했고 결과도 마찬가지로 메모리 초과가 나왔다.

이러한 큰 메모리 문제가 발생하는 경우의 탐색은 이분탐색으로 접근하면 쉽게 해결할 수 있다.

 

따라서 많은 고민끝에 다음과 같이 접근하였다.

1	2	3
2	4	6
3	6	9

1) N*N의 모든 수를 구할 필요 없이, 내가 구하고자 하는 K번째 인덱스 까지만 알면 된다.

2) 2차원 배열의 각 칸들의 값은 i*j 형태를 띄므로, 일정한 규칙이 존재한다.

3) 이 규칙에 따르면, 임의의 수 a보다 작거나 같은 수의 개수를 구하는 식이 존재한다.

4) 각 행은 구구단처럼 1단 2단 3단... 식으로 나타나기 때문에 ( a / 행번호 ) 가 그 행에서 구하고자 하는 개수가 된다.

   단, (a / 행번호) 가 N보다 클 경우에는 N이다.

   예를들어, 임의의 수 a를 4라고 했을 때, 1행은 4 / 1 = 4 이지만 N이 3이므로 3개이며

   4 / 2 = 2 이므로 2행은 2개, 4 / 3 = 1 이므로 3행은 1개이다.

 

이러한 접근방식을 이용하여 이분탐색을 진행하여 내가 구하고자 하는 인덱스를 마주하게 되면 정답이 된다.

이분탐색에서 사용했던 방법 똑같이, 내가 구하고자 하는 target(인덱스)가 mid값(임의의 인덱스)보다 작으면 end값을 줄여 탐색 범위를 좁히면 되고,

target이 mid값보다 크면 start값을 높여 탐색 범위를 좁히면 된다.

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

def binary_search(target, start, end):
    while(start <= end):
        mid = (start + end) // 2

        cnt = 0
        for i in range(1, n+1):
            cnt += min(mid//i, n)

        if cnt >= target:
            end = mid-1
        else:
            start = mid+1
    return start


print(binary_search(k,1,n*n))

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !