95. 백준 11053 번 C++ 코드 및 자세한 설명

안녕하세요 코딩하는 덕구입니다.

다이나믹 프로그래밍 문제인 BOJ 11053 번 가장 긴 증가하는 부분 수열 입니다.

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

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

 

먼저 백준 11053 번 C++ 정답 코드입니다. 설명은 아래에 있습니다.

#include <iostream>
#define MAX 1001
int A[MAX];
int dp[MAX] = {0,};
using namespace std;

int main(){
    int N, max = 0;
    cin >> N;

    for (int i = 0; i < N; i++) cin >> A[i];

    for (int i = 0; i < N; i++){
        for (int j = 0; j < i; j++){
            if (A[j] < A[i]){
                if (dp[i] <= dp[j]){
                    dp[i] = dp[j] + 1;
                    if (max < dp[i]){
                        max = dp[i];
                    }
                }
            }
        }
    }
    cout << max + 1;

    return 0;
}

 

문제 요약

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고,

길이는 4 입니다.

부분 수열 중 가장 긴 증가하는 부분 수열의 길이를 찾아 출력하는 문제입니다.

 

문제 접근

예제의 가장 긴 부분 수열을 구하는 방법입니다.

예를들어 수열 A에서 6번째 까지의 가장 긴 부분 수열은

5번째 숫자 까지 가장 긴 부분 수열 + 1이 됩니다.

즉 i 번째 까지의  가장 긴 부분 수열 = i - 1 까지 가장 긴 부분 수열 + 1

 

C++ 코드 구현

먼저 수열 A 를 입력받고, i 번째 수 까지의 가장 긴 부분 수열을 저장할 행렬 dp 를 구현합니다. 

#define MAX 1001
int A[MAX];
int dp[MAX] = {0,};

for (int i = 0; i < N; i++) cin >> A[i];

 

 

이중 for문을 이용하여 i 번 째 부분수열은 i 보다 작은 숫자 중 가장 긴 부분수열 + 1

이 되도록 코드를 작성했습니다.

if dp[i] <= dp[j] (만약 j 번째 부분 수열이 i 번째 까지의 부분수열 - 1 보다 크다면)

i 번째 까지의 가장 긴 부분수열 = j 번째 까지의 가장 긴 부분수열 + 1 (i > j)

int main(){
    int N, max = 0;
    cin >> N;

    for (int i = 0; i < N; i++) cin >> A[i];

    for (int i = 0; i < N; i++){
        for (int j = 0; j < i; j++){
            if (A[j] < A[i]){
                if (dp[i] <= dp[j]){
                    dp[i] = dp[j] + 1;
                    if (max < dp[i]){
                        max = dp[i];
                    }
                }
            }
        }
    }

 

이제 부분수열 중 가장 긴 길이의 부분수열을 출력하면 됩니다.

cout << max + 1;

 

백준 11053 번 가장 긴 증가하는 부분 수열 C++ 최종 코드입니다.

#include <iostream>
#define MAX 1001
int A[MAX];
int dp[MAX] = {0,};
using namespace std;

int main(){
    int N, max = 0;
    cin >> N;

    for (int i = 0; i < N; i++) cin >> A[i];

    for (int i = 0; i < N; i++){
        for (int j = 0; j < i; j++){
            if (A[j] < A[i]){
                if (dp[i] <= dp[j]){
                    dp[i] = dp[j] + 1;
                    if (max < dp[i]){
                        max = dp[i];
                    }
                }
            }
        }
    }
    cout << max + 1;

    return 0;
}

 

백준 11053 번 가장 긴 증가하는 부분 수열 자세한 설명 및 C++ 코드였습니다.

감사합니다.