백준 / 상자넣기 / 1965번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 상자넣기 / 1965번 (실버 2단계)

문제 사이트: https://www.acmicpc.net/problem/1965

 

문제 설명

---

나의 풀이

def solution(n, boxs):
    # dp[i]: boxs[i]를 마지막으로 사용하는 가장 긴 증가 부분 수열의 길이
    dp = [1] * n

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

    return max(dp)


def main():
    n = int(input())
    boxs = list(map(int, input().split()))
    print(solution(n, boxs))


if __name__ == "__main__":
    main()

---

※ 알아야 할 것

Longest Increasing Subsequence문제와 본질적으로 동일합니다!!