백준 1300번 k번째 수 파이썬
문제
입력 , 출력
solution
def bi_search(start, end):
global res
mid = 0
while start <= end:
mid = (start + end) // 2
temp = 0
for i in range(1, n + 1):
temp += min(n, mid // i)
# mid // i 를 하는 이유?
# 해당행에서 mid보다 작은 수를 구하는 방법은
# mid / i 를 하면 해당 행에서 mid보다 작은 수의 개수를 찾을 수 있음
# 하지만 3*3에서 행에 최대 개수는 3인데
# 6/1 을 할 경우에는 6개가 나와서
# mid / i 의 값이n의 값보다 커질경우
# 최대개수인 n을 삽입하는것임
if temp >= m:
# mid보다 작은수의 개수가 m이랑 같거나 크면
# 더 작아져야하기 때문에 end값을 낮춰줌
res = mid
end = mid - 1
else:
start = mid + 1
n = int(input())
m = int(input())
arr = []
res = 0
bi_search(1, m)
print(res)
설명
키포인트
- k번째 수는 최대 k값을 가짐
- k번째의 수 보다 작은 수의 개수를 찾음
- mid의 값보다 작은 수의 개수는
EX) 3 3 에서 7보다 작은 수의 개수는
11 ~ 13 = 3개 = min(n,7/1) = 3
21 ~ 23 = 3개 = min(n,7/2) = 3
31 ~ 3*2 = 2개 = min(n,7/3) = 2
즉 min(n,mid/i)를 n번 하면
mid의 값보다 작거나 같은수의 개수를 찾을수 있음
def bi_search(start, end):
global res
mid = 0
while start <= end:
mid = (start + end) // 2
temp = 0
for i in range(1, n + 1):
temp += min(n, mid // i)
# mid // i 를 하는 이유?
# 해당행에서 mid보다 작은 수를 구하는 방법은
# mid / i 를 하면 해당 행에서 mid보다 작은 수의 개수를 찾을 수 있음
# 하지만 3*3에서 행에 최대 개수는 3인데
# 6/1 을 할 경우에는 6개가 나와서
# mid / i 의 값이n의 값보다 커질경우
# 최대개수인 n을 삽입하는것임
if temp >= m:
# mid보다 작은수의 개수가 m이랑 같거나 크면
# 더 작아져야하기 때문에 end값을 낮춰줌
res = mid
end = mid - 1
else:
start = mid + 1
n = int(input())
m = int(input())
arr = []
res = 0
bi_search(1, m)
print(res)
키포인트
- k번째 수는 최대 k값을 가짐
- k번째의 수 보다 작은 수의 개수를 찾음
- mid의 값보다 작은 수의 개수는
EX) 3 3 에서 7보다 작은 수의 개수는
11 ~ 13 = 3개 = min(n,7/1) = 3
21 ~ 23 = 3개 = min(n,7/2) = 3
31 ~ 3*2 = 2개 = min(n,7/3) = 2
즉 min(n,mid/i)를 n번 하면
mid의 값보다 작거나 같은수의 개수를 찾을수 있음
나머지 설명은 주석
Author And Source
이 문제에 관하여(백준 1300번 k번째 수 파이썬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@slbin-park/백준-1300번-k번째-수-파이썬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)