가장 긴 증가하는 부분 수열 백준 11053

문제

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

리뷰

자신보다 작은 숫자의 개수를 세는 것이 핵심이다.

 

예시 배열 A = [10 , 20 , 10 , 30, 20 , 50] 이고 크기는 6이다.

 

입력 배열은 A[i] 에 인덱스 1부터 저장된다. 길이는 6이니까 A[1] ~ A[6] 까지 숫자가 저장되어 있다.

바깥 for문 i 를 기준으로 (자기자신 A[ 1 ] ) 자신보다 작은 숫자의 개수를 센다.

D[ i ] 배열에 A[ i ] 보다 작은 숫자의 개수를 저장한다.

 

D[i] 값은 안쪽 for문에 들어가기 전에 1로 초기화 된다. (자기 자신의 길이는 1이기 때문이다. )

 

 

    for(i = 1; i <= len; i++){

        D[i] = 1; // 자기자신 길이 1 로 초기화 

        for(j = 0; j <= i; j++){
            if(A[i] > A[j]){
                D[i] = max(D[i], D[j] + 1);
            }
        }
        cnt = max(cnt, D[i]); // 여태 까지 구한 D 배열의 최대값을 기억한다. (답으로 출력)
    } 

예를 들어, i = 2 라면, A[2] 값 20 을 기준으로, A[0] , A[1] , A[2] 의 값을 비교한다.

A[2] > A[1] 인 경우에 if 문에 들어가게 된다. (현재 D[2] 값은 1이다. )

D[2] = max( D[ 2 ] , D[ 2 ] + 1)

​ = max ( 1, 2 )

D[2] = 2 이렇게 저장되고 끝나게 된다.

 

index	0	1	2	3	4	5	6
A [ ]		10	20	10	30	20	60
D [ ]		1	2	1

 

i = 3 이라면, A[3] 값 10을 기준으로 A[0] , A[1] , A[2] , A[3] 과 비교한다.

처음에 D[3] 값은 1이다.

그렇지만 10보다 작은 값이 없으니까 if문에 들어갈 일이 없다. if 문에 들어가지 못하고 종료된다.

 

A [ 4 ] 의 경우를 보자. A[4] 값 30을 기준으로 A[0] , A[1] , A[2] , A[3] , A[4 ] 값을 비교한다.

 

index	0	1	2	3	4	5	6
A [ ]		10	20	10	30	20	60
D [ ]		1	2	1	3

처음에 D[4] 값은 1이다.

if (30 > A[0]) 문을 만족한다. A[0] = 0이다.

D[4] = max ( D[4] , D[0] + 1) 이니까 D[4] = 1 이다.

 

if (30 > A[1]) 문을 만족한다. A[1] = 10 이다.

D[4] = max ( D[4] , D[1] + 1) 이니까 D[4] = 2 이다.

 

if (30 > A[2]) 문을 만족한다. A[2] = 20 이다.

D[4] = max ( D[4] , D[2] + 1) 이니까 D[4] = 3 이다.

 

if (30 > A[3]) 문을 만족한다. A[3] = 10 이다.

D[4] = max ( D[4] , D[3] + 1) == max ( 3 , 2 ) 이다.

따라서 D[4] = 3 그대로 유지된다.

 

if (30 > A[4]) 문을 만족하지 않는다.

 

D 배열을 전부 채운 결과

index	0	1	2	3	4	5	6
A [ ]		10	20	10	30	20	60
D [ ]		1	2	1	3	2	4

D 배열을 하나씩 채울 때 마다, 최대값을 cnt 변수에 기억한다.

최종 결과 4가 답으로 출력된다.

 

 

코드

#include <stdio.h>
#include <algorithm>
using namespace std;

int A[1001];
int D[1001];

int main(void){

     int len = 0, num = 0, cnt = 1;
    int i = 0, j = 0;

     scanf("%d", &len);

     for(i = 1; i <= len; i++){
         scanf("%d", &num);
         A[i] = num;
    } // 입력받기 끝 


    for(i = 1; i <= len; i++){

        D[i] = 1; // 자기자신 길이 1 로 초기화 

        for(j = 0; j <= i; j++){
            if(A[i] > A[j]){
                D[i] = max(D[i], D[j] + 1);
            }
        }
        cnt = max(cnt, D[i]);
    } 

     printf("%d", cnt);

    return 0;
}