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

최장 증가 수열 알고리즘 문제입니다.

일렬로 있는 숫자들에서 숫자를 빼서 오름차순으로 만들때

가장 길게 만들 수 있는 경우의 수를 구하는 문제입니다.

 

ex)

1, 5, 2, 3, 7

=> 1, 2, 3, 7

* 4개

 

1, 6, 2, 5, 7, 3, 5, 6

=> 1, 2, 3, 5, 6

* 5개

 

마지막 숫자부터 풀어나갔습니다.

위의 예제에서 {1, 6, 2, 5, 7, 3, 5, 6}

 

6은 6 -------------- 1가지

5는 5, 6 ------------ 2가지

3은 3, 5, 6 --------- 3가지

7은 7 -------------- 1가지 

5는 5, 7 또는 5, 6 - 2가지

2는 2, 3, 5, 6 ------ 4가지

6은 6, 7 ------------ 2가지

1은 1, 2, 3, 5, 6 ---- 5가지

와 같은 순서로 구했습니다.

 

먼저 각 배열에 1의 값을 넣어주고

뒤의 배열에 숫자들을 비교해서 숫자가 더 높으면

그 숫자의 메모된 값을 가져와서 +1을 넣어주었습니다.

 

#include  
using namespace std; 

int arr[1000]; 
int memo[1000]; 

void init(int x) 
{ 
    for (int i = 0; i < x; ++i) { 
        arr[i] = 0; 
        memo[i] = 1; 
    } 
} 

int main(int argc, char *argv[]) 
{ 
    int x; 
    int result = 0; 
    cin >> x; 
    init(x); 
    for (int i = 0; i < x; ++i) { 
        cin >> arr[i]; 
    } 
    memo[x - 1] = 1; 
    for (int i = x - 1; i >= 0; --i) { 
        for (int j = i + 1; j < x; ++j) { 
            if (arr[i] < arr[j] && memo[i] <= memo[j]) { 
                memo[i] = memo[j] + 1; 
            } 
        } 
    } 
    for (int i = 0; i < x; ++i) { 
        if (result < memo[i]) { 
            result = memo[i]; 
        } 
    } 
    cout << result; 
    return 0; 
}