백준 1817번: 짐 챙기는 숌 (파이썬)

 

알고리즘 분류 : 그리디 알고리즘

 

그리디 알고리즘이면 최선의 방법을 찾는 걸로 알고 있는데 그냥 푼 것 같은 느낌

처음엔 무거운 것부터 정렬해야하나 싶었는데 그럼 무거운 것과 가벼운 것이 하나의 박스에 들어가면 어떻게 계산해야하나 머리가 안돌아갔다

 

그래서 그냥 차근차근 계산해보기로

일단 최대로 필요한 박스는 책의 개수 N개 만큼일 테니 크기가 N인 배열을 생성해서 책의 무게를 하나씩 더해본다

담을 수 있는 최대 무게 M을 넘어가면 다음 상자로 넘어가는 방식으로 진행했다.

 

# n = 책의 개수, m = 상자의 최대 무게
n,m = map(int,input().split())

# 책이 0개가 이상일 때만  
if n != 0:
  n_list = list(map(int,input().split()))
  
  # 무게를 더할 리스트 
  kg = [0 for i in range(n)]
  
  # cnt = 상자가 늘어나는 수..?
  cnt = 0
  for i in range(len(n_list)):
    # 일단 첫 박스에 책을 담고
    kg[cnt] += n_list[i]
    
    # 책의 무게가 상자의 최대 무게를 넘어가면 다음상자에 담기
    if kg[cnt] > m:
      cnt += 1
      kg[cnt] += n_list[i]
      
    # 책의 무게와 상자의 최대 무게가 일치해도 다음 상자 가져오기
    elif kg[cnt] == m:
      cnt += 1
  
  # 안에 책이 들어있는 상자만 세기
  print(len([i for i in kg if i != 0]))

else:
  print(0)