-
1817. [Python]짐 챙기는 숌Python_알고리즘/Silver V 2023. 3. 27. 23:13
1. 문제
https://www.acmicpc.net/problem/1817
1817번: 짐 챙기는 숌
첫째 줄에 책의 개수 N과 박스에 넣을 수 있는 최대 무게 M이 주어진다. N은 0보다 크거나 같고 50보다 작거나 같은 정수이고, M은 1,000보다 작거나 같은 자연수이다. N이 0보다 큰 경우 둘째 줄에 책
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- 구현
- 그리디
3. 파이썬 코드
N,M = map(int,input().split()) # 책이 0개일 경우 if N == 0: print(0) # 그 외의 경우 else: # 책 리스트 생성 book_list = list(map(int,input().split())) # 박스 리스트 생성 box_list = [] # 책 리스트 순회 for i in book_list: # 만약 박스 길이가 0 인경우 => 시작 한 경우 if len(box_list) == 0: # 박스에 i 값을 넣어준다 box_list.append(i) # 그 외의 경우 else: # 박스의 바로 위 책의 무게랑 i 값이 M보다 큰 경우 if box_list[-1]+i > M: # 새로운 박스를 생성하여 i 추가 box_list.append(i) # 그 외의 경우 이전값에 더해준다 else: box_list[-1] += i # 최종적으로 길이 출력 print(len(box_list))
4. 문제를 풀고난 후 생각
- 문제에서 책이 쌓여있는 순서대로 꺼내야 하기 때문에 sort 나 정렬을 사용할 필요가 없다.
- 처음에는 들어올때마다 cnt 라는 변수를 생성하여 하나하나 직접 세는 방식을 선택했다가 조건을 설정하는 것이 까다로워서 리스트를 생성하여 더해가는 방식으로 풀었다.
- 박스를 채워가며 그 이전값에 새로운 값을 더해가며 무게를 초과하는지 안하는지 체크하는 방식으로 리스트에 추가해 나갔다.
- 그리고 최종적으로는 박스의 길이를 출력하여 문제를 해결하였다.
5. 문제를 푸는데 도움이 되는 지식
- 그리디 알고리즘
- 구현
'Python_알고리즘 > Silver V' 카테고리의 다른 글
2740. [Python]행렬 곱셈 (0) 2023.03.31 2535. [Python]아시아 정보올림피아드 (0) 2023.03.29 14916. [Python]거스름돈 (0) 2023.02.02 1439. [Python]뒤집기 (0) 2023.02.01 2581. [Python]소수 (0) 2023.01.21