오늘 풀어본 문제는 ⭐상자넣기(1965) 라는 문제이다.
1. 문제 요약
- 상자의 크기가 일렬로 주어지고, 앞 상자(바로 앞x)가 현재 상자보다 작으면, 현재 상자에 넣을 수 있다.
- 한 번에 넣을 수 있는 최대 상자 개수?
2. 입출력
입력
- 상자의 개수 (1 ≤ n ≤ 1000)
출력
넣을 수 있는 최대의 상자 개수
3. 알고리즘
- 그리디 아닌 이유 -> 현재 상자를 뒤에 등장할 상자에 넣을 수 있는지 없는지 현재 시점에서 알 수 없음.
- DP 문제
그 중에서도 LIS(최장 증가 부분 수열) 문제임
