[AC] 1965 상자넣기

출처 : https://www.acmicpc.net/problem/1965

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.12/1965.cpp

구직활동으로 거의 안풀었고 풀어도 올리지 않다가 이제 다시 블로그 작성 시작!

먼저 이 문제는 어떻게 봐도 다이나믹프로그래밍이라는것을 어필하고 있는 문제이다. 최대 개수를 구하라는 것은 완탐 or DP일텐데 만약 완탐으로 접근한다면 각 입력마다 최대값을 구하기 위해 선택을 하고 또 하는 과정이 있어야 할 것이고 TL을 피하기 위해선 메모이제이션이든 뭐든 미리 기록해놔야할것이다. 즉, 할수있을지 없을지도 미지수이고 굉장히 복잡해진다.

그러므로 간단히 DP를 써보도록 한다. 이 문제의 알고리즘은 LIS(Longest Increasing Subsequence)라는 알고리즘이다. 

이는 최장 증가 수열을 구하는 문제인데 예전에 캐쳐 미사일 문제를 풀때 공부해뒀던 것이다.

간단히 알고리즘을 적어보면 다음과 같은 과정을 밟게 된다.

1. 정답을 담을 배열을 만든 후 입력받은 배열의 한 요소씩 검사를 시작한다.

2. 만약 현재 정답배열의 사이즈가 0이거나 정답배열의 마지막 값보다 현재 검사하는 요소값이 크다면 새로이 추가를 한다.

3. 2번의 과정에 속하지 않는다면, 한칸씩 앞으로 이동하며 2번의 조건이 성립할때까지 인덱스를 탐색한다.

4. 그리고 최종적으로 배열의 크기를 출력하면 된다. 

이게 알고리즘의 전부인 굉장히 단순한 풀이이다. 예를 들면 다음과 같다.

예제를 보면 

1 6 2 5 7 3 5 6 인데

처음 1 6까진 증가수열이므로 그대로 두고 2가 들어오면

1 2 가 되며 6이 사라진다.

그리고 5 7까지는 그대로 다시 추가되어 1 2 5 7 이 구성된다.

그 후 3이 들어오게 되면 1 2 3 7 이 되고 순차적으로 5와 6이 추가되어 1 2 3 5 6

으로 최종 5가 출력되게 된다.

물론 이 풀이는 그닥 빠른 방법이 아니며 더 빠른 방법이 있다. 하지만 이 방법만 알아도 많은 문제를 풀 수 있으므로 알아두는게 좋다.

구현 방법은 사람마다 다를 것이기 때문에 굳이 나처럼 풀지 않아도 된다. 늘 강조하지만 알고리즘은 하나여도 풀이 방법은 수만가지가 나오는것이 프로그래밍이다.