백준(BOJ) 1965번 상자넣기

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

입력

파일의 첫 번째 줄은 상자의 개수 n (1 ≤ n ≤ 1000)을 나타낸다. 두 번째 줄에는 각 상자의 크기가 순서대로 주어진다. 상자의 크기는 1,000을 넘지 않는 자연수이다.

출력

첫째 줄에 한 줄에 넣을 수 있는 최대의 상자 개수를 출력한다.

나의풀이: LIS와 동일

코드 ( C ++ )

#include <iostream>

#include <algorithm>

#include <cstring>

const int MAX = 1000;

int line[MAX];

int cache[MAX];

int N;

using namespace std;

int findLongLength(int begin)

{

int& ret = cache[begin];

if (ret != -1)

return ret;

ret = 1;

for (int next = begin + 1; next <N; ++next)

if(line[next] > line[begin]) // 뒤에 상자가 더 크다면

ret = max(ret, findLongLength(next) + 1); // 자신의 상자는 포함되는 것이니 1을 더해주고 다시 재귀함수 호출.

return ret;

}

int main()

{

memset(cache, -1, sizeof(cache));

cin >> N;

for (int i = 0; i < N; ++i)

cin >> line[i];

int result = 0;

for (int i = 0; i < N; ++i) {

result = max(result, findLongLength(i));  // 시작상자를 0부터 N번까지 하여 최대 상자 개수를 출력한다.

}

cout << result << endl;

return 0;

}