백준 1654 python

문제

https://www.acmicpc.net/problem/1654

1. 이진탐색

---

import sys
input = sys.stdin.readline
K, N = map(int, input().split())
number = []
for _ in range(K):
  number.append(int(input()))
min = 0
max = max(number)
mid = int((max+min)//2)
while True: 
  count = 0
  for i in range(K):
    count += number[i] // mid
  if count >= N:
    print(mid)
    break
  mid = int((min+mid)//2)

이게 아직 안 되는데 안 되는 이유를 모르겠다. 그래도 다시 계속 볼 예정이다.

2. 이진탐색 반복

---

import sys
input = sys.stdin.readline
K, N = map(int, input().split())
number = []
for _ in range(K):
  number.append(int(input()))
min = 1
max = max(number)

while min <= max: 
  mid = (max+min)//2
  count = 0
  for i in range(K):
    count += number[i] // mid
  if count >= N:
    min = mid+1
  else:
    max = mid-1

print(max)

3. 이진탐색 재귀

---

import sys
input = sys.stdin.readline
K, N = map(int, input().split())
number = []

for _ in range(K):
  number.append(int(input()))
max = max(number)

def counting_binary(n):
  count = 0
  for item in number:
    count += item // n
  return count

def recursion(min, max, N):
  if min>max:
    return max
  mid = (max+min)//2
  count = counting_binary(mid)
  if count>=N:
    return recursion(mid+1, max, N)
  else:
    return recursion(min, mid-1, N)

print(recursion(1, max, N))

하면서 알게된 것들

---

for _ in range(num):

python에서는 반복 작업의 경우(여러 문장을 입력받거나 출력하는 것) for _ in range(num)을 사용할 수 있다.

그래서 for _ in range(K): number.append(int(input())) 이렇게 입력받는 것이 가능하다.

https://stackoverflow.com/questions/66425508/what-is-the-meaning-of-for-in-range $\larr$를 참고 했다.

readline vs input

readline

전

K, N = map(int, input().split())

for i in range(K):
  number.append(int(input().strip()))

import sys K, N = map(int, sys.stdin.readline().split())
여기서 이게
input = sys.stdin.readline으로 정리되는 건 java와 비슷했다.

후

import sys
input = sys.stdin.readline
K, N = map(int, input().split())

for _ in range(K):
  number.append(int(input().strip()))

https://developeryuseon.tistory.com/90 $\larr$ 이 글을 참고했다.

궁금한 것

#1에서 min은 0으로 했을 때 왜 작동하지 않을까?