[BOJ] 백준 2229번 문제 풀이 (Python)

1. 문제 풀이 방법

하나의 수열을 전체로 생각했을 때 조가 잘 짜여진 정도가 큰 지 아니면 나눠서 생각했을 때 조가 잘 짜여진 정도가 큰 지를 비교해서 더 큰 값을 저장하는 방식으로 memoization을 구현해서 풀었다.

이를 간단하게 표현하면 아래와 같다.

• $S_n: \text{score of n-th student ordered by age}$
• $dp[i] = \underset{ 0\le j \lt i}{max} \bigg(dp[j] + max(S_{j+1},\cdots, S_i ) - min(S_{j+1}, \cdots,S_i)\bigg)$

Python에 내장된 max 함수와 min함수의 시간 복잡도가 $O(n)$이기 때문에 max 함수와 min함수를 그대로 사용할 경우 $O(n^3)$이 되어 시간 초과가 발생한다.

미리 다른 배열을 통해 $max(S_{j+1},\cdots, S_i ) - min(S_{j+1},\cdots,S_i)$ 값을 구하여서 최종적으로 $O(n^2)$ 알고리즘을 구현해내었다.

오랜만에 동적계획법 문제를 푸는 것도 있고 시간초과가 발생하지않게 알고리즘을 만드는 것도 있고 해서 난이도에 비해 시간이 오래 걸렸다.

2. 풀이

import sys
def input(): return sys.stdin.readline().rstrip()

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

# diff[i][j]: scores[j:i+1]의 최댓값과 최솟값의 차이
diff = [[0] * n for _ in range(n)]
for i in range(n):
    max_n, min_n = -1,1e10
    for j in range(i,-1,-1):
        if max_n < scores[j]: max_n = scores[j]
        if min_n > scores[j]: min_n = scores[j]
        diff[i][j] = max_n - min_n
        
dp = [0] * n
max_n, min_n = -1,1e10
for i in range(n):
    if scores[i] > max_n: max_n = scores[i]
    if scores[i] < min_n: min_n = scores[i]
    dp[i] = max_n - min_n
    for j in range(i):
        if dp[i] < dp[j] + diff[i][j+1]:
            dp[i] = dp[j] + diff[i][j+1]
print(dp[n-1])