[백준(BOJ)] 11053번 가장 긴 증가하는 부분 수열 C++

문제 : https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

어떤 문제인가?

수열 A 중 가장 긴 증가하는 부분 수열의 길이를 출력하면 된다.

 

증가하는 부분 수열 = 부분 수열이여야 하고 원소들이 오름차순 이어야 한다.

이 중 길이가 가증 큰 것을 찾으면 된다.

 

접근 방법

이 문제는 dp를 통해 접근하였다.

 

int arr[1001];
int dp[1001];

n이 1000까지 입력될 수 있으므로 그에 맞게 수열을 저장할 arr과 dp값을 저장할 dp를 선언해준다.

 

int n;
cin >> n;

n을 입력받는다.

 

 

int cnt = 0;

cnt는 가장 긴 부분 수열의 길이를 저장할 변수이다.

부분수열의 길이가 음수일 수는 없으므로 0으로 초기화해준다.

 

 

for (int i = 0; i < n; i++) {
    cin >> arr[i];
    int standard = 0;

    for (int j = 0; j < i; j++) {
        if (arr[i] > arr[j]) {
            standard = max(dp[j], standard);
        }
    }
    dp[i] = standard + 1;
    cnt = max(cnt, dp[i]);
}

반복문을 통해 수열을 입력받는다.

 

그리고 또 반복문을 통해 비교를 해준다.

만약 i번째 수열 값이 j번째 수열 값보다 크다면 기준이 되는 standard와 dp [ j ]를 비교해 더 큰 값을 standard로 바꿔준다.

 

그리고 dp [ i ] 값은 반복문을 통해 계산된 standard + 1로 해준다.

또다시 cnt와 dp [ i ] 값을 비교해 더 큰 값을 cnt로 해준다.

 

 

cout << cnt;

cnt 값을 출력해주면 끝!

 

 

무엇이 어려웠는가?

그냥 머리 속으로 생각한 내용을 처음부터 빠뜨리는 부분없이 따라 코드로 작성하다보니 큰 어려움은 없었다.