백준(BOJ) 3366 수열 줄이기(Python)

문제 내용

 

스택 문제.

reduce 연산의 비용의 합을 최소로 하기 위해서는, 수열의 최솟값부터 reduce를 해주면 된다.

어짜피 reduce를 진행해나가게 되면 어떤 수 양 옆에 존재하는 수는 절대 작아질 수 없기 때문이다.

즉, 어떤 수가 수열의 최솟값인 경우가 그 수에 대해 reduce를 진행했을 때 reduce의 최솟값인 것이다.

이를 이용하면 쉽게 문제를 해결할 수 있다.

수열의 처음부터 내림차순으로 stack에 수를 집어넣다가 현재 집어넣는 수가 내림차순을 만족하지 않는 경우 reduce를 진행하면 된다.

왜냐하면, 내림차순을 만족하지 않는 수가 등장하게 되면 그 순간 스택의 수들 중 스택의 맨 위에 위치한 수(a)가 현재까지 확인한 부분수열의 최솟값이고, 위에서 설명한 알고리즘대로 문제를 해결하면 되는 것이다.

위의 경우 a를 먼저 pop하고, a의 양 옆 수를 비교해 그 중 더 작은 수와 reduce를 진행하고 ans에 비용을 추가한다.

그렇게 수열의 모든 값을 체크한다.

그러나 이렇게 진행하고 나면, 내림차순인 부분수열이 stack에 남게 된다.

이때는 stack이 내림차순으로 구성되어 있으므로 stack의 맨 위에 위치한 수를 제외한 나머지 수들을 모두 ans에 더하면 수열에 대해 reduce를 모두 적용한 비용이 나온다.

stack의 맨 아래에는 수열에서 등장할 수 있는 가장 큰 수보다 1 큰 수를 넣고 시작해 스택이 비는 것을 방지하고, reduce를 진행할 때 분기를 줄였다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n=int(input())
L=[int(input()) for i in range(n)]
stack=deque()
stack.append(1000000001)
p=1
ans=0
i=0
while i<n:
    if L[i]<stack[p-1]:
        stack.append(L[i])
        p+=1
        i+=1
    else:
        x=stack.pop()
        p-=1
        if stack[p-1]<L[i]:
            ans+=stack[p-1]
        else:
            ans+=L[i]
stack.pop()
p-=1
while p>1:
    ans+=stack.pop()
    p-=1
print(ans)

 

PS에 흥미가 좀 붙는 듯 하다가 갑자기 흥미가 좀 떨어졌다.

1일 1문제씩 의무적으로 푸는 게 다인데, 흥미를 다시 붙여야 할 것 같다.