백준 알고리즘

백준 - 1817번 짐 챙시는 숌 python 문제풀이 [Hellfer]

Hellfer 2024. 1. 18. 22:52
728x90

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

 

1817번: 짐 챙기는 숌

첫째 줄에 책의 개수 N과 박스에 넣을 수 있는 최대 무게 M이 주어진다. N은 0보다 크거나 같고 50보다 작거나 같은 정수이고, M은 1,000보다 작거나 같은 자연수이다. N이 0보다 큰 경우 둘째 줄에 책

www.acmicpc.net

🔷 알고리즘 분류 - 구현, 그리디 알고리즘 

난이도 - 실버 5

그리디 알고리즘(또는 탐욕 알고리즘)은 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 문제를 해결하는 알고리즘입니다. 

 

이 방식은 각 단계에서 가장 좋은 선택만을 하도록 하므로 '탐욕적'이라는 이름이 붙었습니다.

그리디 알고리즘의 가장 큰 특징은 각 단계에서의 최적의 해가 전체 문제에 대한 최적의 해라는 가정하에 동작한다는 점입니다. 

 

따라서 그리디 알고리즘은 항상 최적의 결과를 보장하진 않지만, 계산 속도가 빠르기 때문에 효율적인 해결책을 찾는 데 도움이 됩니다.

예를 들어, 거스름돈 문제에서 가장 큰 단위의 동전부터 최대한 많이 거슬러 주는 방법이 그리디 알고리즘의 한 예입니다. 

 

이 방법은 각 단계에서 가장 좋은 선택 (가장 큰 단위의 동전을 최대한 많이 거슬러 주는 것)을 하므로 '탐욕적'입니다.

파이썬에서 그리디 알고리즘은 주로 반복문을 통해 구현하며, 각 단계에서의 최적의 선택을 계산하는 데 다양한 기법을 사용합니다. 

 

이는 문제의 특성에 따라 다르지만, 정렬이나 우선순위 큐 등을 활용하는 경우가 많습니다.

🔶문제 풀이 - 구현을 이용한 풀이

# n: 책의 개수, m: 박스의 최대 무게를 공백으로 구분하여 입력받는다.
n, m = map(int,input().split())

# 책의 개수가 0이 아닐 경우
if n != 0:
    # 책들의 무게를 공백으로 구분하여 입력받는다.
    x = list(map(int,input().split()))
    # 마지막에 박스의 최대 무게보다 1 큰 값을 추가하여 마지막 박스를 세는 데 도움을 준다.
    x.append(m+1)
# 책의 개수가 0일 경우
else:
    x = []

# 박스에 담긴 책들의 무게 합을 저장하는 변수
result = 0
# 사용한 박스의 개수를 저장하는 변수
count = 0

# 책들을 하나씩 확인하면서
for i in x:
    # 현재 책을 담았을 때 박스의 무게가 m을 초과하지 않으면
    if result+i <= m:
        # 책을 박스에 담는다.
        result += i
    # 현재 책을 담았을 때 박스의 무게가 m을 초과하면
    else:
        # 새로운 박스를 사용하고, 그 박스에 현재 책을 담는다.
        result = i
        count += 1

# 사용한 박스의 개수를 출력한다.
print(count)

🔶 문제 이해하기

아래 예시는 6권의 책이 있고 각 책의 무게가 모두 5이며, 박스의 최대 무게가 10인 경우입니다.

 

6 10
5 5 5 5 5 5


코드를 실행하면 다음과 같이 동작합니다:

책의 무게가 모두 5이므로, x 리스트는 [5, 5, 5, 5, 5, 5, 11]이 됩니다. 

 

여기서 마지막의 11은 박스의 최대 무게보다 1 큰 값으로, 마지막 박스를 세는 데 도움을 줍니다.


박스의 무게 합(result)과 박스의 수(count)를 0으로 초기화합니다.


책들을 순서대로 확인하면서 박스에 담습니다. 

 

만약 박스에 담았을 때 박스의 무게가 m을 초과하면 새로운 박스를 사용합니다.


1. 첫 번째 책을 담으면 result는 5가 되고, m을 초과하지 않으므로 같은 박스에 계속 담을 수 있습니다.


2. 두 번째 책을 담으면 result는 10이 되고, m을 초과하지 않으므로 같은 박스에 계속 담을 수 있습니다.


3. 세 번째 책을 담으려고 하면 result는 15가 되는데, 이는 m을 초과하므로 새로운 박스를 사용해야 합니다.

 

따라서 count를 1 증가시키고, result를 현재 책의 무게인 5로 업데이트합니다.


이 과정을 모든 책에 대해 반복하면, count는 총 3이 됩니다.


사용한 박스의 개수인 count를 출력합니다. 따라서 이 경우의 결과는 3이 됩니다.


즉, 이 예제에서는 6권의 책을 3개의 박스에 담을 수 있습니다. 

 

각 박스에는 무게가 5인 책 두 권씩 담을 수 있습니다.

 

아래 예시는 5권의 책이 있고 각 책의 무게가 모두 51이며, 박스의 최대 무게가 100인 경우입니다.

 

5 100
51 51 51 51 51

 

코드를 실행하면 다음과 같이 동작합니다:

책의 무게가 모두 51이므로, x 리스트는 [51, 51, 51, 51, 51, 51, 101]이 됩니다. 

 

여기서 마지막의 101은 박스의 최대 무게보다 1 큰 값으로, 마지막 박스를 세는 데 도움을 줍니다.


박스의 무게 합(result)과 박스의 수(count)를 0으로 초기화합니다.


책들을 순서대로 확인하면서 박스에 담습니다. 

 

만약 박스에 담았을 때 박스의 무게가 m을 초과하면 새로운 박스를 사용합니다.


1. 첫 번째 책을 담으면 result는 51이 되고, m을 초과하지 않으므로 같은 박스에 계속 담을 수 있습니다.


2. 두 번째 책을 담으면 result는 102가 되고, m을 초과하므로 새로운 박스를 사용해야 합니다.

 

3. 세 번째 책을 담으려고 하면 result는 51이 되는데, 이는 m을 초과하지 않으므로 같은 박스에 계속 담을 수 있습니다.

 

4. 네 번째 책을 담으면 result는 102가 되고, m을 초과하므로 새로운 박스를 사용해야 합니다.

 

5. 다섯 번째 책을 담으려고 하면 result는 51이 되는데, 이는 m을 초과하지 않으므로 같은 박스에 계속 담을 수 있습니다.

 

6. 여섯 번째 책을 담으면 result는 102가 되고, m을 초과하므로 새로운 박스를 사용해야 합니다.

 

따라서 count를  5 증가시키고, result를 현재 책의 무게인 51로 업데이트합니다.


이 과정을 모든 책에 대해 반복하면, count는 총 5가 됩니다.


사용한 박스의 개수인 count를 출력합니다. 따라서 이 경우의 결과는 5가 됩니다.


즉, 이 예제에서는 5권의 책을 6개의 박스에 담을 수 있습니다. 

 

각 박스에는 무게가 51인 책 한 권씩 담을 수 있습니다.

728x90