[python] 백준 25214. 크림파스타

문제

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

민겸이는 크림 파스타를 먹다가 다음과 같은 문제를 생각해냈다.

빈 배열 A가 있다. 민겸이는 A의 맨 뒤에 정수를 N번 추가하려고 한다. 수를 그냥 추가하기만 하면 재미없으니, 수를 추가할 때마다 1 ≤ i ≤ j ≤ |A| 를 만족하는 정수 i, j에 대하여 Aj−Ai의 최댓값을 구하려고 한다. |A|는 배열 A의 현재 길이를 뜻하고, Ai는 민겸이가 i번째로 추가한 정수를 뜻한다.

민겸이가 식사를 마치기 전에 이 문제를 대신 풀어보자.

입력

입력은 두 줄로 주어진다.

첫 번째 줄에는 민겸이가 배열에 추가하려는 정수의 개수 N이 주어진다.

두 번째 줄에는 A1부터 AN까지 N개의 정수가 공백으로 구분되어 주어진다.

출력

각 Ai가 추가된 직후의 문제의 답 N개를 공백으로 구분하여 출력한다.

---

풀이

푸는데 많이 헤맸지만, 결과적으로는 이전에 계산한 값과 현재의 값을 비교하고... 이전에 계산할 때 사용했던 최소값을 사용해서 문제를 해결하면 되는 문제였다.

 

import sys

n = int(input())
a = []
data = list(map(int, sys.stdin.readline().split()))
result = []

mi = data[0]
ma = 0
result.append(0)

for i in range(1, n):
    ma = max(ma, data[i] - mi)
    result.append(ma)
    mi = min(mi, data[i])

sys.stdout.write(" ".join(map(str,result))+' ')

 

1. list와 map을 이용해서 int형으로 data란 배열 만들기

2. 최솟값과 최댓값을 저장해놓을 변수를 선언

3. 맨 앞을 결과적으로 무조건 0이기 때문에 result 배열에 추가

4. for문을 통해 배열 1번째 부터 돌면서 현재 배열에서 mi(최솟값)을 뺀 값과 0을 비교해 큰 값을 result 배열에 넣고

5. 현재 배열 돌면서 온 숫자와 이전 최솟값을 비교하여 더 작은 숫자를 mi(최솟값) 변수에 넣어준다.

6. 그러고 map으로 출력

 

막 삼중...이중 for문으로 적었다가 겨우겨우 O(n)에 맞췄다. 왜냐하면... 이 for문은 배열의 크기만큼 한번만 돌기 때문이다. 

그래.. DP란 이런 법...다이나믹하다 정말..