이진탐색 핵심

• 이진탐색을 하는 경우
  • 데이터 범위가 10,000,000을 넘어가는 경우(천만 이상 초대량의 탐색 필요 시)
    

---

• 링크 : https://www.acmicpc.net/problem/1654
  
  

• 추가 테스트 케이스 모음(반례 정리)
  

---

메모

• k개 랜선에서 각각 잘라야함 (두 개 랜선을 붙일 수 없음)

• 이때 각각 자른것들의 개수의 합이 N이 되어야함

  • 그리고 N개는 전부 길이가 동일해야 함

• 자를 때 정수로만 잘라야. (203.11이런게 남으면 안됨)

• 일단 sort하고,

• 주어진 랜선 중 가장 작은값을 기준으로 뭔가 하면 될거같은데

  • 랜선 중 가장 작은값 하나 잡아서 A라고 할 때,

  • while돌리면서 A의 중간값을 target으로 설정 -> 이 target으로 다른 랜선들 잘라보고

  • if num < k 이면 나와서 A의 중간값의 중간값을 다시 target으로 설정 -> 반복

  • 이때 int(pivot계산한거) = target 으로 해야함!!(정수!!)

  • min으로 다른 랜선들을 자른값(나눠기의 몫값 = 개수니까) 얘를 ans += 해주면 되지 않을까

  • 그래서 ans < N이면 다시 돌리고, == 면 끝?

• 이진탐색은 어케되는겨

---

이진탐색 쓰는 이유 (중요)

• 내가 생각한 방식에서, 랜선 중 가장 작은 애를 기준으로 자르면
• -1씩 해가면서 브루트폴스 하면서 길이를 재봤어야함!
• 그러나 이진탐색 수행하면, -1씩 안하고 큼직큼직 절반씩 잘라나가서
• 시간과 연산량을 매우 매우 단축시킬 수 있음!

• 이처럼 브루트폴스할 때 계산할 범위가 엄청 커질 수 있는 경우 이진탐색 실시!

---

첫 접근

• 문제의 테케는 맞췄는데, 추가 테케되도록 고쳐봐야함
• 그리고 코드가 너무 지저분함!!!

def make_target(start,end):
    return (start+end) // 2

k, n = map(int,input().split())
#arr = [int(input()) for i in range(k)]
arr = [802, 743, 457, 539]
#arr = [2,1,2,1]

start = 1
end = min_num
num_of_rans = 0

min_num = min(arr)

if min_num == 1: target = 1
else: target = make_target(start,end)

while 1:
    for card in arr:
        num_of_rans = num_of_rans + int(card // target)

    # 개수가 부족 = target(pivot)을 더 줄여서 개수를 늘려줘야함
    if num_of_rans < n:
        print(target,num_of_rans)
        end = target-1        
        target = make_target(start,end)
        
    # 개수가 많다 = target(pivot)을 키워서 개수 줄여야함
    elif num_of_rans > n:
        print(target,num_of_rans)
        start = target+1        
        target = make_target(start, end)

    # 찾았다!
    else:
        break
        
    num_of_rans = 0   # 초기화는 필수
    print("------------------------------")
    
print(target,num_of_rans)

---

블로그 솔루션

• 링크 : https://claude-u.tistory.com/443
  

• 들어있는 랜선 중 하나 골라서 걔의 길이로 이진탐색하며 쳐내는 문제였다.

• 내가 놓친거 (핵심 아이디어)

  • 1. 일단 같거나 많으면, 조정도 해줘야함
  • 2. pivot을 출력하게되면, start가 될수도, end가 될수도 있음 (while문 종료조건)
       - 따라서 가장 큰 값을 출력하는 것이므로 end를 도출해야 함
  • 3. max()를 end로 둬야한다. <----이거때문에 계속 틀림

k, n = map(int,input().split())
arr = [int(input()) for i in range(k)]

# 놓친거 3. max()를 end로 둬야한다. <----이거때문에 계속 틀림
start, end = 1, max(arr)

while start <= end:
    num_of_rans = 0              # 여기 넣어주면 자동 초기화

    target = (start+end) // 2    # 함수 만들 필요 없다. 그냥 베이직 코드로!
    
    # Main Idea - 랜선별로 각각 계산 후 add
    for card in arr:
        num_of_rans = num_of_rans + int(card // target)

    # 개수가 부족 = 더 작은 단위로 쪼개서 개수를 세야함(수를 늘려야함)
    # = end위치 절반 아래로 조정해서 그 위치와 start의 중간으로 탐색 시작
    if num_of_rans < n:
        end = target-1
        
    # 개수가 많다 = 더 큰 단위로 쪼개서 개수를 세야함(수를 줄여야함)
    # 놓친거 1. 일단 같거나 많으면, 조정도 해줘야함
    elif n <= num_of_rans:
        start = target+1

# 놓친거 2. pivot을 출력하게되면, start가 될수도, end가 될수도 있음 (while문 종료조건)
#    -> 따라서 가장 큰 값을 출력하는 것이므로 end를 도출해야 함
print(end)