[python] 백준 - 1965. 상자 넣기

🤔문제 해결

• S2 | DP

[python] 백준 - 11055. 가장 큰 증가 부분 수열

위의 문제와 살짝 비슷한 느낌이다.

• 값이 1로 셋팅된 길이가 n 인 dp 리스트를 만든다. dp = [1, 1, 1, ... ]
• 각각의 값은 현재 포함한 상자의 갯수이다.
• 맨앞의 상자부터 하나씩 뒤로가며 앞의 상자를 몇개나 담을 수 있는 지 체크한다.
• 만약 내앞의 상자가 나보다 작고 그 상자가 담고 있는 상자의 갯수(본인포함)가 5개라면
  지금 나의 상자는 앞의 상자까지 담을 수 있으므로 6이 된다.

 

💻소스 코드

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

dp = [1] * n
for i in range(1, n):
    tmp = 0
    for j in range(i - 1, -1, -1):
        if boxes[j] < boxes[i]:
            tmp = max(dp[j], tmp)

    dp[i] += tmp

print(max(dp))

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

1965번: 상자넣기