[백준] 1300 K번째 수

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

초기에 딕셔너리를 이용하여 각 숫자의 값들이 몇개씩 있는지 모두 정의한 후 탐색하려는 인덱스의 값이 어떤 값인지 탐색하였습니다.

그러나 메모리 초과 문제가 발생하였습니다.

 

이 후 이분탐색을 이용하여 해결하였습니다.

2) 알고리즘

• 이분탐색

3) 풀이 코드

사용 언어 - Python

import sys

N = int(sys.stdin.readline())   # 배열의 길이
K = int(sys.stdin.readline())   # 찾으려는 인덱스 번호
answer = 0                      # 정답

low, high = 0, K                # 정답의 최소 숫자, 최대 숫자
while low <= high:              # 이분탐색
    mid = (low+high) // 2       # 정답으로 올 현재 숫자 선택
    cnt = 0

    for i in range(1, N+1):     # 2차원 배열의 모든 행 탐색
        cnt += min(mid//i, N)   # 각 행에 현재 숫자보다 작은게 몇개인지 카운트
    
    if cnt >= K:                # K번째 이후의 숫자라면
        high = mid - 1          # 정답으로 작성
        answer = mid
    else:                       # K반째 숫자 이전이면
        low = mid + 1

print(answer)

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

이분 탐색으로 접근하기 어려웠습니다.

(1) 참고 사이트

• 블로그
  이분탐색의 조건 중 각 행에서 내가 찾으려는 수보다 작은 값이 몇개 있는지 찾는 조건을 학습하였습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

- https://www.acmicpc.net/problem/1300

1300번: K번째 수

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다