https://school.programmers.co.kr/learn/courses/30/lessons/42885?language=python3#
문제
문제 설명
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
- 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.
입출력 예
| people | limit | return |
|---|---|---|
| [70, 50, 80, 50] | 100 | 3 |
| [70, 80, 50] | 100 | 3 |
시도
첫 번째 시도
def solution(people, limit):
cnt = 0
alone = limit - 39 # 혼자타야되는 몸무게
people.sort() #몸무게순 정렬 (alone 구역 찾기)
for i, p in enumerate(people):
if p >= alone : #alone 구역 찾으면
cnt += len(people[i:]) #그 사람들은 혼자 타야함
people=people[:i] #alone 구역 삭제
break
go = [True]*len(people) #검사할지 말지
for i, p in enumerate(people): #2명끼리 탑승
if go[i] == False : continue #이미 태운사람이면 검사x
if len(people)>=2: #alone들 다 태우고 남은사람 두명 이상일 때
if limit-p in people[i+1:] and go[people.index(limit-p)]!=False:
go[i]=False;
go[people[i+1:].index(limit-p)]=False;
cnt += 1 #limit 딱맞게 태우기
else :
max = limit-p #가장 근접한 몸무게 찾기
for j in range(i+1, len(people)):
if p + people[j] < 100:
max = j
go[i], go[max] = False, False # limit에 근접하게 태우기
cnt +=1
if len([True for t in go if t]) < 2 : break #다 태웠으면 끝
else : cnt += 1
return cnt내가 한 생각은 아래와 같다.
두사람을 더했을 때 최대한 100에 맞춰야함
현재 숫자가 40이면 100-40인 60이 있는지 찾아야함
찾기에 성공하면 둘다 빼버림
=>찾기에 실패하면 60이하인 수 중에서 가장 근접한 수를 찾아야함
=>현재 사람을 제외한 나머지들 중에서 최대값 검사
만약 limit-현재몸무게 < 최저몸무게 이면 혼자 타야함
결과
;;;;
두 번째 시도
def solution(people, limit):
cnt = 0
alone = limit - 39 # 혼자타야되는 몸무게
people.sort() #몸무게순 정렬 (alone 구역 찾기)
for i, p in enumerate(people):
if p >= alone : #alone 구역 찾으면
cnt += len(people[i:]) #그 사람들은 혼자 타야함
people=people[:i] #alone 구역 삭제
break
go = [True]*len(people) #검사할지 말지
True_people = len(people) #검사할 사람
for i, p in enumerate(people): #2명끼리 탑승
if go[i] == False : continue #이미 태운사람이면 검사x
if len(people)>=2:
max = -1 #가장 근접한 몸무게 찾기
for j in range(i+1, len(people)):
if p + people[j] <= limit and go[j]:
max = j;
else : break
if max != -1:
go[i], go[max] = False, False # limit에 근접하게 태우기
cnt +=1
True_people -= 2
if True_people < 2 : #다 태웠거나 한명 남았으면 끝
cnt += True_people
break
else : cnt += 1
return cnt
결과
최종 풀이
그래 역시..! 저렇게 긴 코드가 필요할 리 없다ㅋㅋㅋㅋㅋㅋ(참고)
def solution(people, limit):
answer = 0
people = sorted(people)
front = 0 #리스트 앞부분
back = len(people)-1 #리스트 뒷부분
while front <= back: #back이 아직 front앞에 있을 때
answer += 1 # 사람을 태운다
if people[front] + people[back] <= limit: # 앞부분과 뒷부분 합이 작을때
front += 1 # 앞부분을 다음 원소로 옮긴다 (큰 숫자로)
back -= 1 # 뒷부분을 앞 원소로 옮긴다 (작은 숫자로)
return answer반례만 얻으려고 했는데 설명을 봐버렸다.. 이렇게나 깔끔하게 쓸 수 있다!!
주석 흐름따라 이해하면 되는데, front와 back으로 리스트를 검사하면서 사람을 태운다고 생각하면 된다.
테스트케이스로 알아보는 흐름
[40, 45, 50, 60, 70], 100
- front = 0, back = 4:
40+70은 100을 초과하므로 back을 60자리로 옮긴다.
사람을 한 명 태웠다. (answer+=1)- front = 0, back = 3
40+60은 100이하이므로 front는 45자리로 옮기고 back은 50자리로 옮긴다.
사람을 두 명 태웠다. (answer+=1)- 45+50은 100이하이므로 front는 50자리로 옮기고 back은 45자리로 옮긴다.
사람을 두 명 태웠다. (answer+=1)- back이 front 뒤에 있으므로 반복을 끝낸다.
결과
후기
그리디를 풀면 풀수록 느끼는 것이, 복잡하게 생각하면 산으로 간다는 것이다.
최대한 심플하게 생각하는 것이 중요하다.
(그 심플한 생각이 어려워서 그렇지)
