백준 1434 : 책 정리(그리디)*

www.acmicpc.net/problem/1434

1434번: 책 정리

 

문제 요약:

빈 박스 N개, 넣어야 하는 책 M개. (둘다 번호 매겨져 있음)

다음 순서로 책을 박스에 넣는다.

1번 박스 앞에 1번 책을 들고 있음.

(## 1. 현재 책이 현재 박스에 들어가지 않으면 --> 3번 스텝 or 2번 스텝 으로 이해를 했는데...

 ##3번으로 가란 말이 3번 박스가X, 3번 순서O )

 

Step 1. 현재 책이 현재 박스에 들어가는 지 판단. 

            --> 현재 책이 현재 박스에 들어가면  Step2로
            --> 현재 책이 현재 박스에 안들어가면 Step3으로

Step 2. 현재 책을 현재 박스에 --> 다음책 들고 Step1로

Step 3. 현재 박스를 다른 쪽으로 치운 후, 밀봉 --> 다음 박스를 앞으로 가져오고 Step1 로

 

전체 박스의 낭비된 용량의 합은?

Input : N, M = 빈 박스, 책

           A_i = 박스의 용량

           B_i = 책의 크기

 

def solve(N,M,capa_box, size_book):
    ans = 0
    for book in size_book: # 책(book)을 손에 들고
        for i in range(N):  ## box 에 넣을 건데 
            # 들어가는 지 확인을 하고   
            if capa_box[i] >= book : 
                ## 들어가면 box의 용량 사용
                capa_box[i] -= book  
                break # for문 나가서 다음 책으로
            else:
                ans+= capa_box[i] # 낭비된 양 저장
                capa_box[i] = 0 # 아무 책도 못들어가게 capacity 0으로 밀봉
                
    return ans+sum(capa_box)
            
                
        

if __name__=='__main__':
    N,M = list(map(int,input().split()))
    capa_box = list(map(int,input().split()))
    size_book = list(map(int,input().split()))
    ans = solve(N,M,capa_box, size_book)
    print(ans)
    

 

박스의 남은 용량을 capa_box에 저장하고, 사용하면 사용한만큼 빼주면서 업데이트를 했다.

책을 못넣어서 밀봉하면, 밀봉하기 전에  낭비되는 양을 저장하고, capa_box[i]=0으로 만들어준다.

그러면, 다음 책을 들고 만난 박스에서, capa_box가 book을 담을 수 없으므로 항상 else문으로 넘어가게 된다.

책에 대한 for문을 다 돌고 난 후에, 박스에 남은 용량이 있으면 더해준다 ( sum(capa_box) )