#2512 예산

1. 구해야 하는 것
   -> 배정된 예산들 중 최댓값
2. 구하는데 필요한 기준
   -> 총 예산(의 아래인지)

기존 풀었던 문제와 유사해서 무난하게 풀었다!
다른 점은 예산 배정하는 방식이 좀 달랐던 것 같은데
상한액을 정해놓고, 그거보다 작으면 기존 금액, 그거보다 크면 상한액으로 예산을 배정하는 것!

이를 아래처럼 조건문을 통해 구현하였다.

        for i in request: 
            if i>=mid:
                total+=mid
            else:
                total+=i

성공한 코드

import sys

n=int(sys.stdin.readline().rstrip()) #지방의 수
request=list(map(int,sys.stdin.readline().split())) #각 지방의 예산 요청
m=int(sys.stdin.readline().rstrip()) #총 예산

def binary_search(target,start,end):
    result=0

    while(start<=end):
        total=0
        mid=(start+end)//2

        for i in request: 
            if i>=mid:
                total+=mid
            else:
                total+=i

        if total>target:
            end=mid-1
        else:
            result=mid
            start=mid+1

    return result

request.sort()

print(binary_search(m,0,max(request)))

#1072 게임

1. 구해야 하는 것
   -> 게임을 해야하는 최소 횟수
2. 구하는데 필요한 기준
   -> 승률

승률은 백분율로 변환한 후 버림 하는 것이 중요하고 이외에는 다른 문제와 비슷하다.
근데 계속 틀려서 도대체 뭐가 문제지 했는데
승률 변환 식을

math.trunc(y/x*100)

에서

math.trunc(100*y/x)

로 바꾸니까 성공했다...
왜그런건지는 이해하는데 실패.. ^_ㅠ

성공한 코드

import sys
import math

x,y = map(int,sys.stdin.readline().split())

def binary_search(start,end,target):
    result=0

    while(start<=end):
        mid=(start+end)//2

        #해당 횟수(mid)만큼 게임을 한다했을 때, 승률이 어떻게 되는지 확인
        rate=math.trunc((y+mid)/(x+mid)*100)
        
        if rate<=target:
            start=mid+1
        else :
            result=mid
            end=mid-1
    
    if result==0:
        result=-1
    
    return result

print(binary_search(1,x,math.trunc(100*y/x)))

#y/x*100 을 100*y/x로 했더니 성공... 

#2343 기타레슨

1. 구해야 하는 것
   -> 블루레이 크기의 최소
2. 구하는데 필요한 기준
   -> 블루레이의 개수 M

블루레이 크기(mid)를 기준으로 블루레이 개수를 세는 과정이 다른 문제들과 다르다!

성공한 코드

import sys

n,m = map(int,sys.stdin.readline().split()) #강의의 수, 블루레이 개수
length=list(map(int,sys.stdin.readline().split())) #각 강의의 길이

def binary_search(start,end,target):
    result=0
    while(start<=end):
        
        mid=(start+end)//2
        
        #해당 블루레이 크기(mid)를 했을 때 나오는 블루레이 개수는 몇개인가
        cnt=1
        tmp=0
        for i in length:
            if tmp+i>mid:
                cnt+=1
                tmp=0
                tmp+=i
            else :
                tmp+=i
        
        if cnt>target:
            start=mid+1   
        else:
            result=mid
            end=mid-1
            
    return result

#length.sort()

print(binary_search(max(length),sum(length),m))

#2776 암기왕

이게 조금 다른 문제들과 형식이 다른 편이었는데, 수첩2에 적힌 숫자들을 기준으로 하나씩 돌아가며 해당 숫자가 수첩1에 적혀있는지 이진탐색을 진행하면 된다!
이진탐색 로직 자체는 해당 문제가 제일 간단했다.

성공한 코드

import sys

def binary_search(start,end,target):

    while(start<=end):
        mid=(start+end)//2

        #print(target,mid, note_1[mid])
        if note_1[mid]<target:
            start=mid+1
        elif note_1[mid]>target:
            end=mid-1
        else: 
            return 1
    
    return 0

case=int(sys.stdin.readline().rstrip()) #테스트 케이스 수

for _ in range(case):
    num_1=int(sys.stdin.readline().rstrip())
    note_1=list(map(int,sys.stdin.readline().split())) #수첩 1에 적힌 숫자
    num_2=int(sys.stdin.readline().rstrip())
    note_2=list(map(int,sys.stdin.readline().split())) #수첩 2에 적힌 숫자

    note_1.sort()
    for i in note_2:
        print(binary_search(0,len(note_1)-1,i))

#6236 용돈관리

1. 구해야 하는 것
   -> 인출해야 할 최소 금액 K
2. 구하는데 필요한 기준
   -> 인출 횟수 M

그치만 번역본이라 그런지 문제를 이해하는게 너무너무 어려웠다...

첫번째 의문점
통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 토장에 집어넣고 다시 K원을 인출한다.
-> 그러면 결국 인출할 수 있는 최대 금액은 K원 이라는 건가? 만약 하루에 써야되는 돈이 K보다 큰 금액이 나오면 어떡하지? 그때마다 break를 걸어주면 되는건가??
-> (인출할 수 있는 금액)K의 최소를 max(money)로, 최대를 sum(money)로 줌으로써 해결

두번째 의문점
정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다.
-> 인출하고 말고를 지맘대로 정할 수 있다는건가? 이걸 코딩으로 어케 구현함??
-> 해당 인출 횟수보다 작은 범위를 모두 K와 같다고 생각하면 됨...

이 두개를 해결한 후에는 쉽게 풀 수 있었는데 계속 테스트 케이스만 맞고 틀렸다고 나오길래
검색을 통해 여러 코드를 훑어본 후

        cnt=1
        tmp=mid #인출 금액 K로 초기화
        for i in money:
            if tmp-i>=0: #하루에 쓸 돈을 써도 돈이 부족하지 않을 때
                tmp=tmp-i
            else: #돈이 부족할 때
                cnt+=1 #인출 횟수++
                tmp=mid #인출 금액 K로 초기화

K(mid)원 기준으로 하루 하루 쓴 돈을 차감하는 방식으로 짠 코드를

        cnt=1
        tmp=0 #쓴 금액 저장
        for i in money:
            if tmp+i>mid: #만약 오늘까지 쓸 돈을 더했을 때 인출 금액 K보다 크다면
                tmp=i #쓴 금액을 i(오늘 쓸돈)으로 초기화
                cnt+=1 #인출 횟수++
            else: #오늘까지 쓸 돈을 더했을 때 인출 금액 K보다 작다면
                tmp+=i 

위와 같이 0원 기준으로 하루 하루 쓴 돈을 적립하는 방식으로 변경하였더니 성공하였다.

성공한 코드

import sys

n,m = map(int,sys.stdin.readline().split())
money = [int(sys.stdin.readline().rstrip()) for _ in range(n)]

#이진탐색 함수
def binary_search(target,start,end):
    result=0
    while(start<=end):

        mid=(start+end)//2
        
        cnt=1
        tmp=0 #쓴 금액
        for i in money:
            if tmp+i>mid:
                tmp=i
                cnt+=1
            else:
                tmp+=i
                
        if cnt>target:
            start=mid+1
        else:
            result=mid
            end=mid-1

    return result
    
print(binary_search(m,max(money),sum(money)))