[BOJ] 백준 11053 가장 긴 증가하는 부분 수열 / 동적 계획법(Dynamic-Programming)

이미지를 클릭하면 문제 사이트로 이동합니다.

---

 

 

💣 문제 이해

 

 

수열 A = {10, 20, 10, 30, 20, 50}인 경우

 

가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

동적 계획법(Dynamic Programming) 방식을 사용했다.

 

 

💭 풀이 과정

 

 

생각보다 풀이과정은 간단했다.

 

계속해서 DP 문제를 풀이하며 풀이 접근 방식 감을 잘 잡는 게 중요한 것 같다.

 

 

동적 계획법 풀이

 

 

작성 언어: C++

 

#include <cstdio>

using namespace std;


int longestSeqLength(int (*dpArr)[1010], int arrSize) {
    int max = 0, longest = 0;
    for (int i = 0; i < arrSize; ++i) {
        for (int j = 0; j < i; ++j) {
            if ((*(dpArr))[i] > (*(dpArr))[j]) {
                if ((*(dpArr + 1))[j] > max) {
                    max = (*(dpArr + 1))[j];
                }
            }
        }
        (*(dpArr + 1))[i] = max + 1;
        if (longest < (*(dpArr + 1))[i])
            longest = (*(dpArr + 1))[i];
        max = 0;
    }
    
    return longest;
}

int main() {
    int arrSize = 0, answer = 0;
    int dpArr[2][1010] = {0,};
    
    scanf("%d", &arrSize);
    
    for (int i = 0; i < arrSize; ++i) {
        scanf("%d", &dpArr[0][i]);
    }
    
    answer = longestSeqLength(dpArr, arrSize);
    printf("%d\n", answer);
    
    return 0;
}

 

 

Max: 0, Longest: 1

10	20	10	30	20	50
1

 

첫 번째 수는 자기 자신 밖에 없으므로 최대 길이가 1이다.

 

 

 

Max: 1, Longest: 2

10	20	10	30	20	50
1	2

 

두 번째 수는 앞의 수 최대 길이가 1 이므로 자신을 포함해서 최대 길이가 2이다.

 

 

 

Max: 0, Longest: 2

10	20	10	30	20	50
1	2	1

 

세 번째 수는 자신보다 작은 수가 없으므로 최대 길이는 1이다.

 

 

 

Max: 2, Longest: 3

10	20	10	30	20	50
1	2	1	3

 

네 번째 수는 앞의 수 최대 길이가 2 이므로 자신을 포함해서 최대 길이가 3이다.

 

 

 

Max: 1, Longest: 3

10	20	10	30	20	50
1	2	1	3	2

 

다섯 번째 수는 앞의 수 최대 길이가 1 이므로 자신을 포함해서 최대 길이가 2이다.

 

 

 

Max: 3, Longest: 4

10	20	10	30	20	50
1	2	1	3	2	4

 

마지막 수는 앞의 수 최대 길이가 3 이므로 자신을 포함해서 최대 길이가 4이다.

 

 

 

매 차례마다 최대 길이를 갱신한 결과, 4가 가장 긴 증가하는 부분 수열의 길이임을 알 수 있다.

 

 

 

🏆 배운 점

 

 

학기가 시작하면서 꽤 오랜만에 백준 문제를 푼 것 같다.

 

다시 풀어보니 DP 풀던 접근 방법이 기억나기 시작하는 것 같다.

 

자주, 꾸준히 문제 풀이를 하는 것이 중요한 이유를 깨닫게 된다.