[Algorithm] Baekjoon 1965번 : 상자넣기

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

1965번: 상자넣기

int n;
int boxes[1001] = { 0 };
int dp[1001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> boxes[i];
    }
 
    dp[0] = 1;
    int answer = 0;
    for (int i = 1; i <= n; ++i)
    {
        dp[i] = 1;
 
        for (int j = 1; j < i; ++j)
        {
            if (boxes[i] > boxes[j])
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
 
        answer = max(answer, dp[i]);
    }
 
    cout << answer;
}
 

LIS문제랑 거의 동일하다 (최장증가부분수열)

혹시나 까먹지 말아야할 건, 출력해야되는 값은 DP[N]이 아니란것만 잊지말자.

갱신할때마다 따로 최대값을 갱신해줘야한다.