[python] 백준 2229 조 짜기

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

2229번: 조 짜기

문제 해결

사실 딱히 좋은 아이디어가 생각이 안났다.

DP를 이용해 풀어야 겠다는 생각을 했는데 사실 시간복잡도가 커서 마음이 안들었다.

 

import sys
input = sys.stdin.readline
INF = sys.maxsize
n = int(input())
A = list(map(int, input().split())) # value: 점수 index: 나이
dp = [0]*(10000)
if n ==1:
    print(0)
    exit()
dp[1] = abs(A[1]-A[0])
dp[2] = max(dp[0]+abs(A[2]-A[1]),dp[1])
for i in range(3,n):
    for j in range(1,i+1):
        dp[i] =  max(dp[i-j]+max(A[i-j+1:i+1])-min(A[i-j+1:i+1]),dp[i])
print(max(dp))

for문 두개에, max, min 까지... 시간복잡도는 상당했다.

 

최적화의 답을 검색해서 알아봤다.

최적화

import sys
input = sys.stdin.readline
INF = sys.maxsize
n = int(input())
A = list(map(int, input().split())) # value: 점수 index: 나이
dp = [0]*(10000)
for i in range(n):
    dp[i+1] = dp[i]  # dp[i+1]을 A[i]까지 원소로 이루이전 최고 점수합을 이야기한다.
    minval = maxval = A[i]
    j = i-1
    while j>=0 and (A[j]<minval or A[j]>maxval):
        minval, maxval = min(A[j], minval), max(A[j], maxval)
        dp[i+1] = max(dp[i+1], dp[j]+maxval-minval)
        j -= 1
print(dp[n])