백준 15487

문제 링크

문제 설명.

임의의 배열 A가 주어졌을 때, 순서가 있는 4개의 인덱스 i<j<k<l에 대하여, A[j]-A[i]+A[l]-A[k]의 최댓값을 구하는 문제이다.

잡담.

우선 결과적으로 주어진 채점이 되는 시간을 보았을 때 이를 polynomial time으로 변환해보면 O(n) 으로 푸는 것을 요구하는 것 같다.(python 기준,O(n**2)까지 자체적으로 줄여봤으나 시간초과, 실재로 채점하는데 걸리는 시간을 보면 python3 기준으로 좀 아슬아슬한 결과인 1.656초/2초가 나왔다.) 최근 두달 이내로 코딩테스트에 미쳐있었을 때 건들였다가 내팽개치고 다시 풀었지만 아마 내가 쓴 방식으로 로직을 짜는게 거의 유일하다 싶은 풀이라는 생각이 든다.(내가 모르는 더 효율적인 방법이 있을 수는 있다.)

풀이 설명.

dp를 이용한, 배열을 2개를 활용해서 푼 문제.(받은 배열 : lst) 하나는 A[j]-A[i]를 i를 기준으로 계산해서 채운 배열(dp)이 되고, 다른 하나는 A[l]-A[k]를 k를 기준으로 계산해서 채운 배열(dp_end)를 만들었다. 그리고 마지막으로 for문을 한번 더 돌려서 dp[i]+dp[i+1]의 값이 최대가 되는 것을 출력하면 된다.

DP 구현방법에 대한 설명에 앞서 dp와 dp_end를 구현하는 방식은 iterator의 순서만 반대로 되면 되기 때문에 dp를 만드는 방법만 소개할 예정이다.
우선 i를 기준으로 dp를 만들 예정이기 때문에 초깃값의 index는 1, 그리고 초깃값은 dp[1]에 들어간다. 그리고 결과적으로 우리가 구해야 하는 것은 A[j]-A[i]의 최댓값이기 때문에 for문 안에서 2가지를 체크를 해야한다.
lst[:j]에 lst[j]가 추가되었을 때

1. lst[j]가 기존의 lst[:j]의 최솟값보다 작은 경우 최솟값을 변경(minf = lst[j]).
2. lst[j]가 기존의 lst[:j]의 최댓값보다 크거나 이전 loop에서 minf의 값이 변경되서, 이 두 값의 차이가 그전에 등록된 dp[j-1]보다 큰 경우, 최댓값을 변경(maxf = lst[j]) 후, 차이의 최댓값을 업데이트(dp[j] = maxf-minf).
3. 2번이 아닐 경우 dp[j]는 dp[j-1]을 상속.

이때 2,3번은 하나의 if~else문으로 묶이고, 1번은 따로 if문으로 처리해줘야 할 필요가 있다(dp가 만들어져야 하기 때문에).

답안 코드.

from sys import stdin
n = int(stdin.readline())
lst = list(map(int,stdin.readline().strip().split()))

dp = [None for _ in range(n)]
dp_end = [None for _ in range(n)]
dp[0] = -1e9
dp_end[-1] = -1e9
minf = lst[0]
maxf = lst[1]
dp[1] = lst[1]-lst[0]
for j in range(1,n-2):
    if lst[j]-minf>dp[j-1]:
        maxf = lst[j]
        dp[j] = maxf-minf
    else:
        dp[j] = dp[j-1]
    
    if lst[j]<minf:
        minf = lst[j]

minl = lst[n-2]
maxl = lst[n-1]

dp_end[n-2] = lst[n-1]-lst[n-2]
for k in range(n-3,1,-1):
    if maxl-lst[k]>dp_end[k+1]:
        minl = lst[k]
        dp_end[k] = maxl-minl
    else:
        dp_end[k] = dp_end[k+1]
    
    if lst[k]>maxl:
        maxl = lst[k]

result = -1e9
for i in range(1,n-2):
    result = max(result,dp[i]+dp_end[i+1])

print(int(result))