[파이썬] 백준 11399 : ATM

[파이썬] 백준 11399 : ATM

https://www.acmicpc.net/problem/11399

11399번: ATM

실버 3

그리디 알고리즘, 정렬

---

접근

 

3 1 4 3 2를 2 5 1 4 3 순서로 접근한다는 것은 오름차순으로 접근하는 것과 같다.

 

 

코드 풀이(124ms)

import sys
input = sys.stdin.readline
N = int(input())
nlst = sorted(list(map(int, input().split())))
S = 0
for i in range(N):
    for j in range(i+1):
        S += nlst[j]
print(S)

 

예제 입력 1의

3 1 4 3 2를 오름차순 정렬하면

1 2 3 3 4가 된다.

문제의 답은

(1) + (1+2) + (1+2+3) + (1+2+3+3) + (1+2+3+3+4)의 합과 같다.

 

다음은 for문을 한 번 써서 구현한 다른 분의 방법이다.(72ms)

import sys
input = sys.stdin.readline
N = int(input())
nlst = sorted(list(map(int, input().split())))
for i in range(1, N):
    nlst[i] += nlst[i-1]
print(sum(nlst))

 

 

처음엔 문제 접근을 잘못해서 아는 것을 총동원해 열심히 삽질을 했다...