[백준] 1300번 K번째 수

사용 언어 - Python3

1300번: K번째 수 (골드2, 이분 탐색)

문제 ★이분 탐색 문제★

1300번: K번째 수

 

 

정답

i*j 배열의 규칙을 알아내는 이분탐색 문제!! 1~k 범위를 줄여가며 검색한다.

(코드 풀이)

1. 변수 선언

n 배열의 크기

k  b의 인덱스

 

2. 이분 탐색 정의

몇 번째인지 인덱스를 구해야하므로 k의 범위를 이분 탐색한다.

배열은 항상 1*1로 시작하기 때문에, start =1로 한다.

end = k까지만 진행해서 더이상의 불필요한 탐색을 하지 않는다. 

mid는 start와 end의 중간값이다. 

 

2.1. 규칙 찾기

temp = 0 을 선언하고  temp가 k가 될 때까지 이분탐색을 진행한다.

temp += min(mid//i,n)

 

예를 들어, n = 3이면 3*3 행렬이고 이를 오름차순 정렬하면 B = [ 1 2 2 3 3 4 6 6 9 ] 이 된다.

이때 mid = 4 라면 B에서 4(mid)가 있는 인덱스를 찾아야하는 것이다.

B에서 4는 6번째라 B[4] = 6이다. 정답은 6이 된다.

mid가 몇번째 있는지 구하는 과정은 아래와 같다.

mid 값을 n으로 나눈 몫이 n을 넘어가면 n개까지만, n을 넘어가지 않으면 몫을 더해주면 된다. n보다 크면 잘라준다고 생각하자!

아래 그림을 참고하세요 :)

2.2 if문

temp가 k보다 크거나 같으면, temp값을 줄여야 한다. end값을 줄여서 범위를 업데이트한다.

결과값 answer 을 정답 mid로 선언해준다.

temp가 k보다 작으면, temp값을 늘려야 한다. start값을 늘려서 범위를 업데이트한다.

 

3. 출력

answer를 출력해준다.

# 정답 - 이분탐색

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

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

 

---

레퍼런스

• 정답 참고

#396 백준 파이썬 [1300] K번째 수 - 이분탐색

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부