백준 문제풀이 - 1965 번

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

1. 요약 및 풀이방법

정육면체 모양의 상자가 일렬로 놓여있을 때, 앞의 상자가 작으면 뒤에 넣을 수 있습니다.
이때 한번에 넣을 수 있는 최대의 상자 개수를 구하는 문제입니다.

이 문제는 대표적인 동적 프로그래밍 문제인 가장 긴 증가하는 부분수열을 구하는 문제와 동일합니다.
위 알고리즘을 실생활에 적용한 예시로 이해하면 좋습니다.

https://velog.io/@hyungraelee/Python-백준-문제풀이-11053번

2. Code

def main():
    n = int(input())
    boxes = list(map(int, input().split()))
    dp = [1] * n

    for i in range(n):
        for j in range(i):
            if boxes[j] < boxes[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    print(max(dp))

if __name__ == "__main__":
    main()

3. 학습 내용

기본적인 동적 프로그래밍 알고리즘을 다시 복습했습니다.

4. 결과