[백준] BOJ 11399, ATM Python

서론

지난번에는 평범하지 않은 배낭 문제에 대해서 풀어보았다. 해당 문제가 궁금하다면 여기로 가면 된다. 이번에는 BOJ 11399 ATM 문제를 풀어보도록 하겠다. 이번 포스팅 역시 처음에는 문제 푸는 과정을 알려주고 아래에는 코드를 작성해놓을 예정이다. 추가 설명이 필요하다면 그에 따른 설명도 첨언하겠다. 해당 문제는 아래로 가면 된다. https://www.acmicpc.net/problem/11399

 

---

BOJ 11399 문제풀이 과정

우선 브루트포스로 접근을 해보자. 사람들이 기다리는 시간 리스트를 순서와 상관 있게 나열하고 O(n!), 그 때의 각 경우를 시간 계산 O(n) 하면 O(n!)이 나오는데 이렇게 하면 시작하기도 전에 이미 시간이 초과됨을 알 수 있다. 그래서 이 시간을 줄이고자한다. 그래서 예시를 보면서 생각을 해보면 뒤에 위치할수록 앞에 있는 숫자들이 스노우볼처럼 몰려오는걸 알 수 있다. 그럼 스노우볼을 줄이려면? 최대한 작은 놈부터 굴려야 된다. 뒤에 있는 애들이 앞에 숫자만큼 기다린다고 생각하면 될 듯 하다. 결론적으로 풀이 과정은 다음과 같다. 1. 정렬을 해서 작은 값부터 앞에다가 놓는다. 2. tmp라는 변수를 만들어서 여태까지 기다린 시간을 저장한다. 3. 그리고 여태까지 기다린 건 새로운 리스트인 res에 append한다. 4. res의 합을 출력한다.

---

BOJ 11399 코드

n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
tmp = 0
res = []
for i in range(n):
    tmp += arr[i]
    res.append(tmp)
print(sum(res))

나 같은 경우는 개인별 기다린 시간을 따로 저장해서 마지막에 합한걸 출력했는데, 사실 새로운 배열을 만들지 않아도 한번에 구현할 수 있다. arr[i] 대신 i번째 사람이 기다린 누적 시간을 곱해주는 것이다. 가령 [1,2,3,4,5] 이렇게 되어 있다면 1은 총 5번을 더해질 것이고(= 2,3,4,5에게 누적되기에) 2는 3,4,5에게 누적으로 총 3번 ... 이렇게 되기 때문이다. 그래서 이걸 만든 코드는 아래와 같다. sum연산과 따로 arr가 없기에 이게 더 빠른게 이성적으로는 맞는데.. 백준이는 반대로(내 코드가 더 빠른걸로) 나온 건 나도 이해할 수 없다.

n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
ans = 0 
for i in range(n):
    ans += arr[i]*(n-i)
print(ans)