[python] 백준 6198 옥상 정원 꾸미기

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

6198번: 옥상 정원 꾸미기

 

문제 해결

• stack 만으로 사용하기에는 시간초과가 걸려 dp를 이용함
• for문을 통해 기준 빌딩을 잡은 가장 가까운 이전 빌딩부터 차례로 높이를 비교하여 더 큰 빌딩을 잡는다.
• 그 빌딩을 마지막으로 처음 빌딩부터 가장 긴 길이의 감소 수열 길이를 dp를 통해 저장한다.
• 그러면 기준 빌딩은 가장 긴 길이의 감소 수열 길이는 +1이고 그만큼의 정답이 늘어난다.
• 이것도 pypy3로는 통과 (python3로는 시간초과)

 

CODE

n = int(input())
stack = []
answer = 0
dp = [0]*(n+1) # dp[i]는 1~i까지 빌딩중 i를 마지막으로 가장 긴 감소 수열의 원소 개수
for j in range(1,n+1):
    x = int(input())
    i =0
    target = x
    while i<len(stack):
        i += 1
        if stack[-i] > target:
            dp[j] = dp[j-i] + 1
            answer += dp[j]
            break
    stack.append(x)
print(answer)