오늘의 문제
https://www.acmicpc.net/problem/11399
포인트 쳌쳌
그리디 알고리즘(탐욕법, Greedy Algorithm)이란 문제를 해결할고자 하는 그 때, 최적이 되는 해결법을 채택하는 방식의 알고리즘 기법이다.
그리디 문제를 풀 때는 이 문제에서 요구하는 값을 출력하기 위해서는 어떤 것에 초점을 맞춰야 하는지를 빠르게 캐치할 수 있어야 하는 것 같다.
나는 다음과 같은 순서로 생각했다.
- 이 문제는 사람별로 각자의 소요시간이 할당 되어있고 뒷 순서에 위치할 수록 각자가 기다리는 시간은 늘어난다.
- 문제에서는 개개인이 기다리는 시간의 총합이 가장 적을 때. 그것을 찾으라고 했다.
- 총합이 적다는 것은 각자가 적은 시간을 기다림을 의미한다.
- 적은 시간을 기다힌다는 것은 앞에 위치한 사람들이 빠르게 일을 끝냄을 의미한다.
따라서, 소요시간이 적은 순서대로 앞쪽부터 줄을 선다면 총합이 최소가 될 것이다.
첫번째 풀이는 딕셔너리를 이용한 방법이다.
풀이 코드
import sys
n = int(input())
p = list(map(int, sys.stdin.readline().split()))
time = {}
for i in range(n):
#key: 사람번호, value: 그 사람이 가지는 소요시간
time[i] = p[i]
#시간이 적게 걸리는 순으로 정렬, 키값(사람 번호)로 이뤄진 리스트를 반환한다.
time_ = sorted(time, key = lambda x: time[x])
s = 0 #합계
for i in range(len(time_)):
for j in range(i+1):
s += time.get(time_[j])
print(s)
두번째 풀이는 리스트를 이용한 방법이다.
import sys
n = int(input())
p = list(map(int, sys.stdin.readline().split()))
#시간이 적게 걸리는 순으로(오름차순) 정렬
p.sort()
s = 0 #합계
for i in range(len(p)):
for j in range(i+1):
s += p[j]
print(s)
채점 결과
리스트를 사용한 방법이 조금 더 빨랐다.