백준 그리디 문제입니다. 알고리즘 숙달을 위한 문제 반복풀이입니다. 실전에 대비하기 위해 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()한 방식입니다.🐦🐦🐦

감사합니다.