[Python]Baekjoon 1817번: 짐 챙기는 숌

1. 문제

 

https://www.acmicpc.net/problem/1817

1817번: 짐 챙기는 숌

 

책을 담을 수 있는 최소 상자의 갯수를 구하는 문제이다.

 

순서대로 책을 담았을 때 상자가 담을 수 있는 무게를 초과한다면 다음 상자를 꺼내야 한다.

 

2. 풀이

현재 상자에 담을 수 있는 무게를 current라고 하자.

 

담으려고 하는 책의 무게가 current 이하라면 담을 수 있을 것이고, 초과 한다면 새 상자를 준비해야 한다.

 

current 이하라면 담으면 되니까 cnt를 증가시키지 않고 current를 책의 무게만큼 감소시킨다.

 

책의 무게가 current 를 초과한다면 cnt를 1 증가시키고, current를 M으로 초기화한다.

 

while 문을 이용해서 책의 수(i)가 N이 될때까지 반복해주자.

 

아래 코드의 로직을 따르면 마지막 책을 새로운 상자에 담았을 때 cnt 를 증가시키지 않는다.

 

그렇기 때문에 마지막 책까지 담았는데 무게가 있다면 그 상자까지 카운트 해주는 로직을 추가해야 한다!

3. 코드

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

books = list(map(int, input().split()))

current = M

cnt = 0

i = 0

while i < N:

    if current - books[i] >= 0:

        current -= books[i]

        i += 1

    else:

        current = M

        cnt += 1

if current < M:

    cnt += 1

print(cnt)

 

4. 느낀점

그리디 알고리즘에 익숙해질 수 있는 문제였다.

 

파이썬의 for 문은 객체를 까서 가져오는 개념이라 루프 안에서 아무리 i 값을 조절해도 for 루프에서 새로 할당 받는다.

 

즉. i 를 조절하고 싶다면 while 문을 사용해야 한다는 것!

 

그리고 list에 입력받은 원소를 추가하고 싶다면 books = list(map(int, input().split()))

 

books.append(map(int, input().split())) 이렇게 하면 안된다.

 

(map() 함수는 iterable의 각 요소에 대해 함수를 적용하는 객체를 반환한다. books 리스트에는 map 객체가 아니라 값을 담아야 한다. 이를 해결하기 위해 append()를 사용하는 대신에 list() 함수로 map() 객체를 리스트로 변환해야 한다.)

 

오늘 하루도 쌓였다.