백준 그리디 문제입니다. 알고리즘 숙달을 위한 문제 반복풀이입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.
문제
https://www.acmicpc.net/submit/11399
[나의 풀이]
⌛ 시간 초과
(테스트 케이스 시간 초과)
N = int(input())
times = list(map(int,input().split()))
print(times)
# times.sort()
print(times)
import itertools
import math
minium = 0
now_x = 0
for x in times:
now_x += x
minium += now_x
for case in itertools.permutations(times, len(times)):
case = list(case)
print(case)
now = 0
total = 0
while case:
v = case.pop()
now += v
total += now
if total>minium:
break
if total<minium:
minium=total
print(minium)
줄을 선 사람들의 각 대기시간의 총합을 가장 적게하는 케이스를 구하는 문제입니다. 최초 생각할 때는 list.sort(reverse=True)를 활용하여 큰값들을 비교적 적게 더하는 방식까진 생각했었습니다. 하지만 정렬하여 연산하는 것이 꼭 최소값이 아니라고 판단하여 정렬한 상태에서 그 이후까지의 조합까지 확인하여 최소값을 구하는 방식으로 구현하였습니다.🐼🐼🐼
그러나 너무 당연하게도 한번 정렬 후 이전까지의 대기시간을 모두 더하면 되는 간단한 문제였습니다. 너무 어렵게 생각한 것 같습니다...🐥🐥🐥
[다른사람의 풀이1]
n = int(input()) # 첫째줄 입력
peoples = list(map(int, input().split())) # 기다리는 사람들 리스트 형태로 입력 받음
peoples.sort() # 작은 순서대로 정렬
answer = 0 # 정답 변수를 0으로 만듭니다.
for x in range(1, n+1):
answer += sum(peoples[0:x]) # 리스트의 0번째 수부터 x번째 수까지를 더해줍니다.
print(answer) # 정답 제출
저의 풀이와 같은 정렬 후 연산하는 방식으로 sum() 함수와 인덱싱을 통해 구현한 모습입니다.
n = int(input())
time_list = list(map(int, input().split()))
time_list.sort()
for i in range(1, n):
time_list[i] += time_list[i-1]
print(sum(time_list))
또 다른 방식으로써 원본 대기시간 list 요소들에 각각 이전 인덱스에 해당하는 값을 더하여 마지막에 sum()한 방식입니다.🐦🐦🐦
감사합니다.
감사합니다. 이런 정보를 나눠주셔서 좋아요.