[백준][1965번][C/C++] 상자넣기

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

1965번: 상자넣기

문제를 핵심만 남겨서 해석해보자면 다음과 같다.

"정렬되지 않은 정수 배열이 주어질 때 연속적으로 증가하는 가장 큰 정수 배열의 길이를 구하여라"

이는 흔히 LIS (Longest Increasing Subsequence), 즉 최장 증가 부분 수열이라 불리는 문제이다.

다음과 같은 논리로 위와 같은 문제를 DP로 풀 수 있다.

 

먼저, DP 배열은 다음과 같이 선언한다.

DP[지금 탐색 중인 상자의 번호] = 지금 탐색 중인 상자에 넣을 수 있는 최대 상자의 개수

 

그 후 0번째 상자부터 n-1번째 상자까지 차례로 탐색을 시작한다.

지금 탐색중인 상자(지금부터 i상자라고 하겠다)보다 왼쪽에 있는 모든 상자(지금부터 각각 j상자라고 하겠다)에 대해서 다음 2가지를 판단해서 DP값을 갱신한다.

 1. j상자가 지금 i상자보다 더 작은가?  = j상자가 i상자에 들어갈 수 있는 크기인가?

 2. 1번이 해당된다면 이미 내가 알고있는 i상자의 DP값이 더 큰가 아니면 j상자의 최대 상자의 개수 + 1 (지금 i번째 상자)가 더 큰가 판단해서 더 큰 값으로 DP값을 갱신한다.

 

2번의 식은 점화식으로 표현하면 다음과 같다.

DP [i] = max(DP [i], DP [j] + 1)

 

그렇게 모든 DP값을 구한 후, DP 배열에서 가장 큰 수를 출력하면 정답이다.

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

int main() {
    int DP[1001]; // DP[지금 탐색중인 상자의 번호] = 지금 탐색중인 상자에 넣을 수 있는 최대 상자의 개수
    int n, inp, ret = 0;
    vector<int> v;

    scanf("%d", &n);
    for(int i=0;i<n;i++) {
        scanf("%d", &inp);
        v.push_back(inp);
        DP[i] = 0;
    }

    for(int i=0;i<n;i++) {
        DP[i] = 1; // 자기 자신은 무조건 담을 수 있으므로 최대 1은 보장
        for(int j=0;j<i;j++) { // 지금까지 담은 모든 최대 개수 값을 따져서 지금 상자의 최대 개수 값을 구한다.
            if(v[j] < v[i]) { // 지금 상자 안에 담을 수 있다면 
                DP[i] = max(DP[i], DP[j] + 1); // 담는게 더 많은지 이미 알고있는 최대 개수가 더 많은지 확인한다.
            }
        }
        ret = max(ret, DP[i]); // 전체 DP값 중 최대값이 답
    }

    printf("%d", ret);

    return 0;
}