K 번째 수 [ Python ] [ 백준 : 1300 ]

---

풀이 및 회고

 

문제 이해도 어려웠고 정말 정말 정말 정신이 나갈거 같은 문제였다.

단순하게 리스트에 넣어 곱한 값을 출력하였으나 바로 메모리 초과가 발생했다. 

이를 줄여야하는데 이를 위해 규칙성을 찾는 것이 첫번째 목표였다.

1 x 1 = 1

1 x 2 = 2 <-- 중앙값 

1 x 3 = 3

2 x 1 = 2 

2 x 2 = 4 <-- 중앙값

2 x 3 = 6

3 x 1 = 3

3 x 2 = 6 <-- 중앙값

3 x 3 = 9

중앙 값에서 양 옆의 수들을 본인 숫자로 빼거나 더하면 값을 찾을 수 있는 규칙을 발견했고 또

1 x 2 = 2 를 반대로 한다면 2 / 1 = 2 가 된다는 것을 발견해 이분 탐색으로 풀 수 있다는 것을 발견했다.

여기까지 오는데 2시간이 넘게 걸린것 같다.

어우힘들어엌

# k 번째 수
n = int(input())
k = int(input())
# 값을 곱했을때 중간값이 양옆의 수랑 본인 값을 더하가너 뺏을때 값이나옴
# 중앙값을 찾는데 이 중앙값이 k 보다 적다.
# 이분 탐색을위한 start, end 를 선언하고, end = k 와 같은값으로 설정한다.
start, end = 0, k # end = 6, 5
res = 0
# start 가 end 와 같거나 적으면 반복, start 가 end와 같아지거나 커지면 반복문 탈출
while start <= end:
    middle = (start + end) // 2 
    # 0 + 7 // 2 = 3 # 중간값 부터 찾기위해 middle 선언 # 1 + 7 // 2 = 4 # 2 + 7 // 2 = 4 # 2 + 6 // 2 = 4 
    # 2 + 5 // 2 = 3
    result = 0 # 결과 값을 저장할 result 선언
    for i in range(1, n+1): # 1 부터 n + 1 만큼 반복
        result = result + min(int(middle / i), n) # 
        # 7
    if result < k:
        start = middle + 1
    else:
        end = middle - 1
        res = middle

print(res)

아직 골드를 풀기엔 부족한 것 같다. 실버부터 차근차근..