Baekjoon 11399번 ATM

Baekjoon 11399번 ATM

Contents

1. Problem

2. Solution

3. Code

4. Other's Code

5. Shortest Code

1. Problem

1. N = 사람의 수
2. $P_i$ = i 번째 사람이 돈을 인출하는 데 걸리는 시간
3. $\sum_i^N CumSum(P_i)$

2. Solution

	P	CumSum	P	CumSum
1	3	3 (=3)	1	1 (=1)
2	1	4 (=3+1)	2	3 (=1+2)
3	4	8 (=3+1+4)	3	6 (=1+2+3)
4	3	11 (=3+1+4+3)	3	9 (=1+2+3+3)
5	2	13 (=3+1+4+3+2)	4	13 (=1+2+3+3+4)
Sum		39		32

표를 보고 이해하는 것이 훨씬 빠를 것 같습니다.

문제에서 제시한 것을 표로 재구성한 부분이 1,2 열 입니다.

보는 것과 같이 i 번째 사람이 돈을 인출하는데 걸리는 시간이 제각각이지만 i번째 사람이 기다리는 시간과 인출하는 시간을 생각하면 앞의 사람의 영향을 받는 것을 알 수 있습니다.

예를 들어 인 첫 번째 사람은 처음이기 때문에 그대로 3분만이 필요합니다.
그러나 인 두 번째 사람은 인출에 1분밖에 걸리지 않지만 앞에 사람 이 인출하는 시간을 기다려야하기 때문에 앞의 사람이 인출한 시간 + 자신이 인출한 시간을 더해야하는 상황이 됩니다. 이렇게 뒤로가면 갈수록 더 많은 대기시간이 걸리게 됩니다.

그렇다면 언제모든 사람이 인출하기까지의 시간의 합이 최소가 될까요?

i 번째 사람이 돈을 인출하기까지 걸리는 시간 = i-1번까지 인출 시간 + 자신의 인출 시간

i-1번째까지 인출 시간을 줄인다면 i 번째 사람이 인출하기까지 시간이 줄어들 것 입니다.

그럼 문제에서 제시하듯 앞에 사람의 시간이 적게끔 정렬시키고 각각의 를 구해서 각각의 합을 구하면 답이나오겠네요.

3. My Code – 122B 56ms

N=int(input())
s = sorted(list(map(int, input().split())))
cnt = 0
for i in range(N):
    cnt += s[i]*(N-i)   
print(cnt)

다른 사람들에 비해 긴 편이지만 그래도 O(n)으로 56ms를 맞았습니다.

4. Other’s Code – noye – 94B 56ms

input()
a=sorted(map(int,input().split()))
print(sum([a[i]*(len(a)-i)for i in range(len(a))]))

for 문을 list 안에서 돌려서 바로 sum 하도록 만들어 길이를 더 줄였네요.
그리고 처음 줄에 받는 N은 사실 다음 줄에 받는 값들의 길이와 같기 때문에 사실 필요없는 것이지만 의무적으로 받아야하는 stdin이기에 input만 명시하고 따로 사용하지는 않았습니다.
배워야겠습니다.

5. Shortest Code – skygarlics 76B 64ms

input();b=0;t=0
for i in sorted(map(int,input().split())):b+=i;t+=b
print(t)

2째 줄에서 받은 값을 바로 for문에 넣고 sort까지 했는데 이렇게 되면 시간복잡도가 늘어날 것이 분명해보입니다. 때문에 시간도 저보다 코드가 짧았지만 64ms가 나온 것입니다.

여기서 for문에 sorted(input)까지 하면서 시간복잡도를 늘리지 말 것을 배웁니다.

Baekjoon 11399번을 통해 배운 것

• 시간복잡도를 생각한다면 for문의 list를 넣을 때 sorted(map(int, input))형식을 넣지말자.
• Cumurative Sumation 방식을 이해한다.
• Sum(list) 방식을 통해 코딩의 길이를 줄여볼 수 있다.