백준 1965번 상자넣기

문제 링크입니다: https://www.acmicpc.net/problem/1965

사실상 최대 증가부분 수열의 길이 구하기 문제였습니다.

예전에도 LIS 문제를 풀어봤기 때문에 쉽게 구현할 수 있었습니다.

/*

정육면체 모양의 상자들이 일렬로 늘어서 있다.

상자들마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다.

예를 들어 앞에서부터 순서대로 크기가(1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자들을 크기 7인 상자 안에 넣을 수 있다.

하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다.앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자들을 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.

상자들의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 작성하시오.

*/

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MAX = 1000;

 

int N; //상자의 개수

int cache[MAX + 1], box[MAX];

 

//box[start]에서 시작하는 증가 부분 수열 중 최대 길이 반환

int boxLIS(int start) //

{

        int &result = cache[start + 1];

        if (result != -1)

               return result;

 

        result = 0;

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

               if (start == -1 || box[start] < box[next]) //처음 index이거나 전보다 큰 경우

               {

                       int candidate = boxLIS(next) + 1;

                       if (candidate > result)

                              result = candidate;

               }

        return result;

}

 

int main(void)

{

        cin >> N;

        if (N<1 || N>MAX)

               exit(-1);

 

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

               cin >> box[i];

 

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

        cout << boxLIS(-1) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~