[백준1052번] 물병

행렬
사용언어 : python
Greedy Alogorithm
난이도 : 실버1

✍ 문제

💻 코드

✔ 알고리즘 1 (스스로 생각해낸 알고리즘)

N,K=map(int,input().split()) #총 n개의 물병을 한번에 K개 옮길 수 있음


#비어있지 않은 총 물병의갯수
num=N
A=0
rest=[]
#_rest=0
answer=0
i=0

 #현재 담겨있는 물병의 갯수
_sum=N

#그 갯수가 K보다 같거나 작아질때까지 while문 돌림
while _sum > K: 
    if num>1 :
        if num%2==1:#남는 물병이 존재한다는 뜻
            rest.append(2**A)
        num=num//2
        _sum=num+len(rest)
        A+=1
    else:
        if(i<len(rest)-1):
            answer+=rest[i+1]-rest[i]
            rest[i+1]*=2
            _sum-=1
            i+=1
        else:
            if len(rest)==1:
                answer=2**A-rest[0]
                _sum-=1
            else:
                if _sum==2:
                    answer+=2**A-rest.pop()
                break

print(answer) #구매해야하는 물병의 수

💡전체적인 알고리즘 방향

1. K값보다 물이 담긴 병의 갯수가 작아질때까지 while문 돌도록 한다
2. 최대로 같은 양의 물병을 합해준뒤 남았던 물병들은 rest라는 배열에 담아준다.
3. rest리스트가 비어있다면 남은 물병없이 잘 합쳐진것 이므로 answer값은 0
4. 비어있지 않은 rest 리스트에 대해 인덱스값 사이 차이만큼 더해줌으로써 필요한 물병의 갯수를 파악할 수 있음
5. 단, K=1인 경우 break로 if문을 빠져나오는 예외 상황 발생한다.
   이를 해결하기 위해 _sum==2 이 부분 처럼 전체 더해진 A값에서 rest의 마지막 요소사이 차이를 더해줌으로써 상황을 처리하는 방식이다

어려웠던 점 :
위 5번에 대한 상황이 발생한다는 사실을 파악하는데에 시간이 오래걸림
코드가 굉장히 복잡하고 많은 예외상황 고려를 요구
좋은 알고리즘 ❌❌

✔ 알고리즘 2 (인터넷 보고 참고한 알고리즘)

..업데이트 예정 .. 알고리즘1로 풀다가 힘 다빠졌...어..