백준 11399 : ATM (Greedy, Python, 정렬 조건 lambda)

문제 : 

11399번: ATM

오랜만에 그리디 문제도 풀어봤다.

 

그리디로 풀어야되는데 감잃고 고냥 조합으로 구하다가 메모리 초과로 실패 한번 띄우고 정렬해서 다시 풀었다.. (반성중)

 

그리디와 정렬은 뗄 수 없다는 사실!!! 잊지말자!!!!

 

풀이 1

N=int(input())
t=list(map(int,input().split()))
G=[]

for i in range(N):
    G.append((i+1,t[i]))
G.sort(key=lambda x: x[1])
#print(G)
tmp=res=0
for x,y in G:
    tmp+=y
    res+=tmp
print(res)

 

파이썬 sort()는 lamba를 이용해서 정렬 조건을 추가할 수 있다.

 

다중 조건일 때는 튜플을 이용하자  G.sort(key = lambda x : (x[0], -x[1]))

 

 

풀이 2

n=int(input())
p = list(map(int,input().split()))
p.sort()

res=[0]*n
res[0]=p[0]
for i in range(1,n):
    res[i] = res[i-1]+p[i]

print(sum(res))

 

나중에 보니 굳이 튜플로 풀지 않아도 되는 문제여서 다시 풀었다. (속도도 개선됨!)