[백준] 11053번 : 가장 긴 증가하는 부분 수열

문제

 

---

풀이

 

대표적인 동적계획법 문제이다.

증가하는 부분 수열을 담은 max_num이란 배열이 있다고 하자. max_num의 상태는 다음과 같다.

10

20

30

현재 max_num의 길이는 3이니 가장 긴 증가하는 부분 수열의 길이도 3이라고 할 수 있겠다.

이때, 15가 들어오는 경우와 50이 들어오는 경우를 살펴보자.

 

15가 들어오는 경우

가장 오른쪽의 숫자인 30부터 비교를 시작한다. 왜 왼쪽부터가 아니라 오른쪽부터 비교하냐면 우리의 목적은 제일 긴 수열을 찾는 것이고, 가장 큰 수가 오른쪽에 저장됐을 것이다. 새로 들어오는 수가 이 수보다 크다면, 한 번에 수열의 길이를 하나 늘릴 수 있는 것이다.

 

아무튼 30과 비교하니 15<30이라 20과 비교했다. 이번에도 15<20이라 10과 비교 했더니 15>10인 것을 발견할 수 있었다.

그렇다면 15의 위치는 10의 바로 오른쪽이 되는 것이고, 20을 15로 갱신한다.

20을 이렇게 날려도 되나? 생각할 수도 있다. 근데 날려도 된다.

15보다 큰 숫자만 있으면 길이 3의 수열을 만들 수 있는데 굳이 20을 저장해둘 필요는 없다.

아무튼 15가 들어온 뒤 max_num은 이렇게 될 것이다.

10

15

30

 

50이 들어오는 경우

마찬가지로 가장 오른쪽의 숫자인 30부터 비교를 시작한다.

바로 50>30이란 것을 발견한다.

그렇다면 가장 긴 수열의 길이를 하나 늘릴 수 있으니 max_num의 길이를 +1해주고 30의 오른쪽에 50을 저장하면 될 것이다.

10

20

30

50

 

이걸 그대로 코드로 작성한다.

---

소스코드

 

#include <iostream>
using namespace std;

int arr[1001];
int max_num[1001];

int lis(int num) {
    int point = 1;

    max_num[1] = arr[1]; //초기화
    for (int i = 2; i <= num; i++) {
        for (int j = point; j >= 0; j--) {
            if (arr[i] > max_num[j]) { //만약 큰걸 찾으면
                max_num[j + 1] = arr[i]; //갱신 해주는데
                if (j == point) //만약 그게 시작부터 그랬던 거라면
                    point++; //max_num 배열 인덱스도 증가
                break;
            }
        }
    }
    return point;
}

int main() {
    int N;

    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> arr[i];
    cout << lis(N);
}

전체 소스코드이다.

 

    max_num[1] = arr[1]; //초기화
    for (int i = 2; i <= num; i++) {
        for (int j = point; j >= 0; j--) {
            if (arr[i] > max_num[j]) { //만약 큰걸 찾으면
                max_num[j + 1] = arr[i]; //갱신 해주는데
                if (j == point) //만약 그게 시작부터 그랬던 거라면
                    point++; //max_num 배열 인덱스도 증가
                break;
            }
        }
    }

point 변수는 max_num 배열의 가장 오른쪽을 가리키고 있다.

이번에 투입되는 수 arr[i]를 max_num 배열의 가장 오른쪽 수부터 비교해 나간다.

 

arr[i] > max_num[j] 일 때의 경우는 둘로 나눌 수 있다.

앞서 말한 15가 들어오는 경우와 50이 들어오는 경우이다.

 

일단 두 경우 모두 max_num[j+1]에 arr[i]를 넣어줘야 하는 것은 같지만,

j == point 즉, 50이 들어온 경우와 같을 때에는 max_num의 길이를 나타내는 point 변수에 1을 더한다.

 

max_num[0]에 0을 넣어놓았으니, arr[i] > max_num[j]이 아닌 경우는 나오지 않는다.