[ 백준 1965 ] 상자넣기 (C++)

백준의 상자넣기(1965) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 이 문제를 쉽게 말하자면 주어진 수열에서 "가장 긴 증가하는 부분수열"을 구하는 문제이다.

   본인은 이 문제를 해결하기 위해서 입력을 저장하는 배열 Arr[] 1차원 배열과, 최대의 상자갯수를 저장하는 DP[] 배열을

   사용하였다.

   DP[a] = b 의 의미는, "a번 원소까지의 담을 수 있는 최대의 상자갯수는 b개 입니다." 이다.

2) { 1, 2, 5, 4, 7 } 이라는 예제를 통해서 풀이과정을 알아보자.

   먼저 초기 값으로 DP[1] ~ DP[5] = 1 로 저장을 해줘야 한다. 왜냐하면, 자기자신을 선택하는 순간 상자의 갯수는

   자기자신, 최소 1개는 되기 때문이다.

   그렇다면, 지금부터는 첫번째 원소부터 다섯 번째 원소까지 각 원소들을 선택했을 때의 상자의 최댓값을 알아보자.

   최댓값을 구하는 방법은, "자기 자신보다 이전에 있던 원소들을 비교해서 더 작은 값들 중에, 그 원소의 최댓값 + 1을

   한 것이, 기존의 값 보다 더 크다면 선택을 한다." 이다.

   무슨 말인지 하나도 모르겠다. 위의 말을 예를 통해서 구체적으로 알아보자.

   지금부터는 위의 예제의 첫 번쨰 원소부터 다섯 번째 원소까지의 상자의 최댓값을 알아볼 것이다.

   < 첫번째 원소 : 1 >

   사실, 첫 번째 원소 '1' 의 경우 비교할 대상이 없다. 왜냐하면, "자기 자신보다 이전에 있던 원소들을 비교해서 더 작은 값들

   중에.." 라는 말의 조건을 충족시키는 '이전에 있던 원소'가 없기 때문이다.

   그렇다면 DP[1] = 1 로 그대로 남아있을 것이다.

   < 두번째 원소 : 2 >

   "자기 자신보다 이전에 있던 원소들을 비교해서 더 작은 값들 중에..."

   두번째 원소인 '2'보다 이전에 있던 원소로는 '1'이 있다. 게다가, '1'은 더 '2'보다 더 작은 값이다.

   "그 원소의 최댓값 + 1을 한 것이, 기존의 값 보다 더 크면 선택을 해라 !"

   그 원소의 최댓값은 1이다. 첫번째 상자에 담을 수 있는 상자의 최대갯수는 1개이기 때문이다.

   즉, 그 원소의 최댓값 + 1 = 2

      기존의 값 = 1 (DP[2]의 값)

      그 원소의 최댓값 + 1을 한 '2' 라는 값이, 기존의 값 '1' 보다 더 크기 때문에 선택을 해라.

      즉, DP[2] = 2 가 되는 것이다.

   실제로, 두 번째 원소인 '2'를 선택했을 때 담을 수 있는 상자의 최댓값은 2개이다. { 1, 2 } !

   < 세번째 원소 : 5 >

   '5' 보다 이전의 원소들 중 더 작은 값들로는 '1'과 '2' 가 있다.

   먼저 '1'을 비교해보자.

   그 원소의 최댓값 + 1을 한 값이, 기존의 값 보다 더 크다면 선택을 한다.

   DP[1] = 1 이고 이 값에다가 +1을 한 '2'라는 값이, 기존의 값인 DP[3] = 1 보다 크기 때문에 선택을 하게 되면

   DP[3] = 2 가 된다.

   이제는 '2'를 비교해보자.

   그 원소의 최댓값 + 1을 한 값이, 기존의 값 보다 더 크다면 선택을 한다.

   DP[2] 의 값은 현재 2이다. 여기에 + 1을 한 값인 '3' 이라는 값이, 기존의 값인 '2' 보다 더 크기 때문에

   DP[3] = 3 이 된다.

   < 네번째 원소 : 4 >

   4 보다 이전에 있는 원소이면서 더 작은 값 = '1', '2'

   '1'을 선택할 경우 DP[4] = 2

   '2'를 선택할 경우 DP[4] = 3 이 된다. 위의 설명을 읽고 다시 스스로 한번 해보자.

   < 마지막 원소 : 7 >

   7보다 이전에 있는 원소이면서 더 작은 값 = '1', '2', '5', '4'

   '1' 을 선택할 경우 DP[5] = 2

   '2' 를 선택할 경우 DP[5] = 3

   '5' 를 선택할 경우 DP[5] = 4

   '4' 를 선택할 경우 DP[5] = 4

  

   이 후, 이 모든 값을 비교해서 최댓값을 찾아주면 된다.

   마지막으로 풀이를 정리해보자면..

  1. 자기보다 이전의 원소들 중 작은 원소들을 하나씩 모두 비교해보자.

  2. 선택한 작은 원소의 최댓값 + 1을 한 값이, 현재 자기자신의 최댓값 보다 크다면 그 값으로 자기자신의 값을

    갱신

  3. 최댓값을 갱신 !

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 1000 + 1
using namespace std;
 
int N;
int Arr[MAX];
int DP[MAX];
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> Arr[i];
    }
}
 
void Solution()
{
    int max = 0;
    for (int i = 1; i <= N; i++)
    {
        DP[i] = 1;
        for (int j = 1; j < i; j++)
        {
            if (Arr[j] < Arr[i] && DP[i] < DP[j] + 1)
            {
                DP[i] = DP[j] + 1;
            }
        }
        if (max < DP[i]) max = DP[i];
    }
    cout << max << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}