728x90
백준 1092번 그리디 문제에 대한 풀이를 알아보겠습니다. 문제 해설은 링크를 연결해두었으니 확인하시기 바랍니다.
백준 1092번 배 문제 해설
1092번: 배
첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보
www.acmicpc.net
물건을 옮기는데 최적의 방법은 가장 무거운 것을 들 수 있는 크레인이 가장 무거운 박스를 옮기는 것이다. 방법은 다음과 같다.
- 각 크레인과 박스를 무게에 맞게 내림차순 정렬시켜준다.
- 크레인이 들 수 있는 가장 무거운 박스를 옮긴다.
- 모든 크레인에 대해서 해결했다면 시간을 1 올려준다.
- 2의 과정을 반복한다.
상자를 옮기는 최소의 시간은 위의 과정으로 해결이 가능하다. 그렇다면 모든 박스를 옮길 수 없는 경우에 대하여 처리도 해줘야 한다. 옮길 수 없는 경우는 가장 무거운 것을 들 수 있는 크레인보다 무거운 박스가 존재하는 경우이다. 따라서 정렬된 크레인과 박스의 값의 첫 번째 값을 비교해서 박스의 무게가 더 크다면 옮길 수 있는 크레인이 존재하지 않다는 것을 뜻한다.
위의 과정을 코드로 정리하면 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
n = int(input())
data = list(map(int,input().split()))
m = int(input())
weight = list(map(int, input().split()))
timeCount = 0
data = sorted(data, reverse=True)
weight = sorted(weight, reverse=True)
if data[0] < weight[0]:
print(-1)
else:
while len(weight) > 0:
for l in data:
for j in range(len(weight)):
if l >= weight[j]:
weight.remove(weight[j])
break
timeCount += 1
print(timeCount)
|
그래도 조금 생각해보면 최적의 방법을 찾을 수 있는 그리드 문제였습니다.
728x90
'취업을 준비하며 정리하는 컴퓨터 지식 > Problem Solving' 카테고리의 다른 글
[ProblemSolving] 백준 7576번 토마토 문제풀이 (0) | 2021.02.04 |
---|---|
[Problem Solving] 백준 1916번 최소비용 구하기 문제풀이 (0) | 2021.02.02 |
[ProblemSolving] 백준 2589번 보물섬 문제풀이 (0) | 2021.01.29 |
[ProblemSolving] 백준 2667번, 프로그래머스 64061번 문제풀이 (0) | 2021.01.27 |
[ProblemSolving] 프로그래머스 60057번 문자열 압축 문제풀이 (0) | 2021.01.21 |