[그리디] 코딩테스트 문제 TIL (ATM) - 백준 11399번

말하는 감자·2024년 11월 27일

algorithm baekjoon greedy python sorting 그리디 백준 알고리즘 정렬 코딩테스트 코딩테스트 준비 파이썬

코딩테스트 유형별 풀이

목록 보기

27/67

오늘은 그리디 알고리즘 문제를 2문제를 풀었습니다. 그럼 어떤 문제인지 살펴볼까요?

1. 오늘의 학습 키워드

Greedy

2. 문제: 11399. ATM

단계: 🥈실버 5단계
알고리즘 분류:
- 그리디 알고리즘
- 정렬
출처: https://www.acmicpc.net/problem/11399

문제

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

예제 입력 1 복사

5
3 1 4 3 2

예제 출력 1 복사

3. 문제 풀이

Step1. 문제 이해하기

ATM이 주어집니다. 사름은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 $P_i$ 분입니다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 됩니다. 즉, 시간이 누적되어 총 시간이 정해지는 것이죠.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 $P_i$ 가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합이 최솟값을 구하는 문제입니다.

문제의 입력, 출력을 알아보겠습니다.

Input:
- 사람의 수 N, 각 사람이 돈을 인출하는데 걸리는 시간 $P_i$ 가 주어집니다.
- N의 크기는 1이상 1000이하, $P_i$ 의 크기는 1이상 1000이하입니다.
- $P_i$ 의 크기는 시간 복잡도에 여향을 주지 않을것입니다. 해당 리스트의 요소 값이기 때문입니다.
- N의 크기가 시간 복잡도에 영향을 줄 것으로 보이는데 $O(n^2)$ 까지는 무난히 가능합니다.
Output:
- 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 반환합니다.

그럼 문제를 조금 더 자세하게 분석을 진행해보겠습니다.

Step2. 문제 분석하기

이 문제는 일종의 누적합의 최솟값을 구하는 것입니다.

문제의 예시를 보겠습니다.

예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 
2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 
3+1 = 4분이 걸리게 된다. 
3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 
총 3+1+4 = 8분이 필요하게 된다. 
4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 
이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 
1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 
각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다.

위 예시의 두 번째 경우를 보면 뭐가 보이시나요? 바로 걸리는 시간이 작은순으로 정렬을 했습니다. 즉, 한 사람이 돈을 인출하는데 걸리는 시간이 작은 사람부터 인출을 시작하면 모든 사람이 돈을 인출하는데 걸리는 시간이 최소라는 것을 알 수 있습니다.

따라서, 정렬과 누적합을 통해 문제를 해결할 수 있습니다.

그러므로 이 문제는 한 사람이 돈을 인출하는데 걸리는 시간이 최솟값이면, 모든 사람이 돈을 인출하는데 걸리는 시간이 최솟값을 보장하는 그리디 알고리즘입니다.

그럼 코드 설계를 진행해보겠습니다.

Step3. 코드 설계

문제 분석에서 저희는 방법을 거의 다 설계했습니다.

$P_i$ 가 들어있는 리스트를 정렬합니다.
이 리스트를 순회하면서 누적합을 구합니다.

매우 간단합니다!! 바로 코드 구현을 해보겠습니다.

Step4. 코드 구현

import sys

N = int(sys.stdin.readline().strip())
time = sorted(list(map(int,sys.stdin.readline().split())))

def sol(N,time):
    result = 0
    
    for i in range(N):
        for j in range(i+1):
            result += time[j]
    return result
print(sol(N=N,time=time))

코드 설명:

이 코드는 주어진 사람들의 인출 시간을 최소화하기 위해 정렬과 누적합을 이용한 간단한 그리디 알고리즘입니다.

정렬:
- 리스트 time을 sorted()를 이용해 오름차순으로 정렬합니다.
- 작은 시간이 앞에 오도록 하여 누적합을 최소화합니다.
누적합 계산:
- for문을 이용해 첫 번째 사람부터 마지막 사람까지 인출 시간을 계산합니다.
- result 변수에 각 사람의 인출 누적합을 더해줍니다.
- 중첩 for문에서 i번째 사람까지의 인출 시간을 모두 더하는 방식입니다.
결과 출력:
- 최종적으로 계산된 result를 출력하여 최소 인출 시간을 반환합니다.

시간 복잡도: $O(n^2)$

결과:

하지만, 이중 반복문을 사용하지 않고 더 효율적으로 구현할 수 있습니다.

import sys

N = int(sys.stdin.readline().strip())
time = sorted(list(map(int,sys.stdin.readline().split())))
def sol2(N,time):
    result = 0
    curr = 0
    
    for t in time:
        curr += t
        result += curr
    return result
print(sol2(N=N,time=time))

시간 복잡도: $O(nlogn)$

결과:

4. 마무리

이 문제는 그리디 알고리즘의 대표적인 예로, 주어진 조건에서 정렬을 통해 전체 비용을 최소화하는 방식이었습니다. 정렬 이후 누적합 계산 방식을 개선하여 효율성을 높일 수 있었으며, 이를 통해 $O(N^2)$ 에서 $O(N \log N)$ 로 시간 복잡도를 최적화했습니다.