[BOJ][DP] 1965. 상자넣기

문제 -> https://www.acmicpc.net/problem/1965

LCS인가 여튼 이와 비슷하게 접근하여 문제를 해결할 수 있다.

문제를 잘 읽어보아야 하는게, 

입력된 상자의 데이터가 있을 때,

그 데이터의 위치를 가지고 판단을 해야한다.

(처음에 그냥 막무가내로 풀었다가 실패)

또한, 저 상자들을 최대한 넣어서 어떤 무지막지하게 큰 상자에 넣는것이다.

즉, 조건을 만족하는 상자의 개수를 세는 것.

그러면 상자는 어떻게 세느냐?

arr[i]보다 작은 값 arr[x] (x < i) 에 대해 

dp값을 조사한다. 

제일 큰 dp값을 기억해서 + 1. 

1, 5, 2, 3, 7 의 예시로 해보자.

처음에는 모든 값이 0.

1의 왼쪽에는 작은 더 작은 수가 없으므로 그냥 +1.

이어서 "5"는 왼쪽에 더 작은 수인 "1"이 존재.

고로 1의 dp값에 +1.

아래도 위와 같은 방법으로 반복된다. 

이리하여 제일 많이 담을 수 있는 상자는 4개가 되겠다. 

소스(Github)