[백준-11399] ATM 파이썬, 탐욕알고리즘을 이용한 최적해 찾기

# 문제

# 풀이

탐욕 알고리즘(Greedy Algorithim)을 이용해서 최적해를 구하는 방법의 문제라고 생각했다. 탐욕 알고리즘은 현재 상황이 가장 최적이라고 생각하고 문제를 풀어나가는 방법인데, 항상 최적의 해를 구하는 것은 아니다. 때때로는 근사한 값을 구할 수 있다. 

출처 https://velog.io/@contea95/%ED%83%90%EC%9A%95%EB%B2%95%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

위와 같이 6이 최적이라고 판단했지만 사실은 17->23으로 가는 것이 더 최대값을 구할 수 있는 경우가 생기기 때문이다.

이번 문제에서는 위와 같은 경우는 고려하지 않았도 됐기 때문에 그냥 풀었다.

for문을 두 번 돌려서 풀면 당연히 편하겠지만 시간복잡도가 O(n^2)으로 늘어나기 때문에 O(n)으로 풀 수 있는 방법이 있을까 고민했고 아래와 같이 반복문을 한번만 돌려서 정답을 구 할 수 있었다.

# 코드

import sys

def answer(n,p_list) :
  p_list.sort()
  sum = 0
  for i in range(n) :
    if i == 0 :
      sum += p_list[i]
      continue
    p_list[i] = p_list[i] + p_list[i-1]
    sum += p_list[i]
  return sum

if __name__ == '__main__':
    n = int(sys.stdin.readline().strip())
    p_list = list(map(int,sys.stdin.readline().strip().split()))
    result = answer(n,p_list)
    print(result)

 

# 참고