그리디: 백준 11399 파이썬

문제:

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

11399번: ATM

풀이:

이 문제는 단순히 돈을 인출하는데 걸린 시간 P가 저장되어있는 배열을 정렬하고, 누적합을 구하면 되는

문제이다. for문을 두 번 사용해서도 풀 수 있지만, 시간 복잡도를 줄이기 위해 for문을 한 번만 쓰는 방법을 생각하다가 다이나믹 프로그래밍 기법(동적 계획법)을 떠올렸다. 

이 문제는 다이나믹 프로그래밍의 조건인 1. 큰 문제를 작은 문제로 나눌 수 있는가, 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일한가. 이 두가지를 모두 만족하기 때문에 다이나믹 프로그래밍 기법 사용이 가능하다. 

 

리스트 d에 누적합을 저장하고 이 누적합을 total 변수에 더해주는 방식으로 문제를 해결했다.

 

정답:

import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

arr.sort()

d = [0] * 1001

d[0] = arr[0]
total = d[0]

for i in range(1, n):
    d[i] += d[i-1] + arr[i]
    total += d[i]

print(total)