[Python] 1817번 짐 챙기는 숌

✏️ 문제

 

문제 파악

나는 다음과 같이 풀었다. 

m의 값을 어딘가(max_m)에 저장

if 책의 무게 <= 최대 무게
	if 상자 안에 책이 하나도 없다면
		상자를 새로 사용하는 것이므로 상자 개수 +1
    최대 무게 -= 책의 무게
else 책의 무게 > 최대 무게
	최대 무게 = max_m
    상자를 새로 사용해야 하므로 상자 개수 +1

if 최대 무게 == 0
	최대 무게 = max_m

예제로 있던 문제는 다 잘나오는데 제출하면 1%에서 계속 틀렸었다.. 반례...

다른 분은 현재 박스에 넣어져 있는 무게 + 넣을 책의 무게를 최대 무게와 비교하며 풀었었다.

알고리즘은 이게 더 간편한 듯!

 

알고리즘

• 그리디 알고리즘
• 구현

 

 

코드

• 내가 푼 틀린 코드

n,m = map(int, input().split())
box = 0

if n != 0:
  book = list(map(int, input().split()))
  max_m = m

  for i in range(n):
    if book[i] <= m:
      if m == max_m: # 첫 상자 오픈
        box += 1  
      m -= book[i]
    else:
      m = max_m
      box += 1
    
    if m == 0:
      m = max_m

print(box)

• 정답 코드

n,m = map(int,input().split())
box = 0

if n == 0: 
  print(box)
else: 
  books = list(map(int,input().split()))
  weight = 0
  box = 1 
  for book in books:   
    if book + weight <= m: 
      weight += book
    else: 
      weight = book 
      box += 1
  print(box)