BOJ - 1965) 상자 넣기

주어진 상자의 크기가 위와 같이 각각 1, 5, 2, 3, 7 의 경우 1, 2, 3, 7 의 크기 차례로 상자에 넣을 수 있다. 예제의 경우 8개의 상자 크기가 주어질 때 1, 2, 3, 5, 6 의 순으로 상자를 넣는 것이 가장 많은 상자의 개수를 출력하게 된다. 따라서, 해당 문제는 가장 긴 부분 수열과 같은 방법으로 해결하는 문제이다. 

 

가장 긴 부분 수열을 구하는 문제와 같이, 2중 for 문을 활용하여 인덱스 마다 상자를 넣을 수 있는 최대 개수를 갱신하는 DP 알고리즘을 통하여 문제 해결이 가능하다.