[python] 백준 1965 상자넣기

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

1965번: 상자넣기

 

문제 해결

• 이전의 상자들이 영향을 주기 때문에 dp 이용해야 한다는 느낌이 든다.
• 하지만 어느 상자를 마지막에 넣어야 할 지는 잘 알 수 없다.
• 마지막에 넣을 수 있는 상자의 인덱스를 미리 알아본다. (for문을 통해)
• dp[i]를 i상자 안에 있는 최대 상자 개수라고 하면
• for문을 통해 i보다 작은 인덱스 상자 중 넣을 수 있는 상자 최대 개수와 dp[i]를 비교해가며 최댓값으로 dp[i]를 수정해간다.

 

CODE 

import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
dp = [0 for _ in range(n)]
graph = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(i+1,n):
        if A[i] < A[j]:
            graph[i][j] = 1
for i in range(n):
    for j in range(i):
        if graph[j][i] == 1:
            dp[i] = max(dp[j]+1, dp[i])
print(max(dp)+1) # 자기자신 합쳐야하기 때문