[BOJ] 백준 11055 가장 큰 증가 부분 수열 / 동적 계획법(Dynamic-Programming)

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

---

 

 

💣 문제 이해

 

 

수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우 합이 가장 큰 증가 부분 수열은

 

A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

 

 

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

 

 

💭 풀이 과정

 

 

앞의 문제 11053번 가장 긴 증가하는 부분 수열 과 거의 유사하다.

 

 

동적 계획법 풀이

 

 

작성 언어: C++

 

#include <cstdio>


int biggestIncreasingSeq (int arr[][1010], int size) {
    int sumMax = 0, l_result = 0;
    
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < i; ++j) {
            if (arr[0][i] > arr[0][j]) {
                sumMax = arr[1][j] > sumMax ? arr[1][j] : sumMax;
            }
        }
        arr[1][i] = sumMax + arr[0][i];
        if (arr[1][i] > l_result) {
            l_result = arr[1][i];
        }
        sumMax = 0;
    }
    
    return l_result;
}

int main() {
    int seqArr[2][1010] = {0,};
    int numCnt = 0, result = 0;
    
    scanf("%d", &numCnt);
    
    for (int i = 0; i < numCnt; ++i) {
        scanf("%d", &seqArr[0][i]);
    }
    
    result = biggestIncreasingSeq(seqArr, numCnt);
    printf("%d\n", result);
    
    return 0;
}

 

 

 

이번에는 수의 개수를 기록하는 것이 아닌 수의 합을 기록하고, 매번 최대 합을 갱신한다.

 

 

sumMax: 0,  result: 1

1	100	2	50	60	3	5	6	7	8
1

 

첫 번째 수는 자기 자신 밖에 없으므로 부분수열 합이 1 이다.

지금까지 가장 큰 증가 부분수열의 합은 1 이다.

 

 

 

sumMax: 1,  result: 101

1	100	2	50	60	3	5	6	7	8
1	101

 

두 번째 수는 더할 수 있는 수 중 가장 합이 큰 것이 1 이므로 부분수열 합이 101 이다.

지금까지 가장 큰 증가 부분수열의 합은 101 이다.

 

 

 

sumMax: 1,  result: 101

1	100	2	50	60	3	5	6	7	8
1	101	3

 

세 번째 수는 더할 수 있는 수 중 가장 합이 큰 것이 1 이므로 부분수열 합이 3 이다.

지금까지 가장 큰 증가 부분수열의 합은 101 이다.

 

 

 

sumMax: 3,  result: 101

1	100	2	50	60	3	5	6	7	8
1	101	3	53

 

네 번째 수는 더할 수 있는 수 중 가장 합이 큰 것이 3 이므로 부분수열 합이 53 이다.

지금까지 가장 큰 증가 부분수열의 합은 101 이다.

 

 

 

sumMax: 53,  result: 113

1	100	2	50	60	3	5	6	7	8
1	101	3	53	113

 

다섯 번째 수는 더할 수 있는 수 중 가장 합이 큰 것이 53 이므로 부분수열 합이 113 이다.

지금까지 가장 큰 증가 부분수열의 합은 113 이다.

 

 

 

sumMax: 3,  result: 113

1	100	2	50	60	3	5	6	7	8
1	101	3	53	113	6

 

여섯 번째 수는 더할 수 있는 수 중 가장 합이 큰 것이 3 이므로 부분수열 합이 6 이다.

지금까지 가장 큰 증가 부분수열의 합은 113 이다.

 

 

 

sumMax: 6,  result: 113

1	100	2	50	60	3	5	6	7	8
1	101	3	53	113	6	11

 

일곱 번째 수는 더할 수 있는 수 중 가장 합이 큰 것이 6 이므로 부분수열 합이 11 이다.

지금까지 가장 큰 증가 부분수열의 합은 113 이다.

 

 

 

sumMax: 11,  result: 113

1	100	2	50	60	3	5	6	7	8
1	101	3	53	113	6	11	17

 

여덟 번째 수는 더할 수 있는 수 중 가장 합이 큰 것이 11 이므로 부분수열 합이 17 이다.

지금까지 가장 큰 증가 부분수열의 합은 113 이다.

 

 

 

sumMax: 17,  result: 113

1	100	2	50	60	3	5	6	7	8
1	101	3	53	113	6	11	17	24

 

아홉 번째 수는 더할 수 있는 수 중 가장 합이 큰 것이 17 이므로 부분수열 합이 24 이다.

지금까지 가장 큰 증가 부분수열의 합은 113 이다.

 

 

 

sumMax: 24,  result: 113

1	100	2	50	60	3	5	6	7	8
1	101	3	53	113	6	11	17	24

 

열 번째 수는 더할 수 있는 수 중 가장 합이 큰 것이 24 이므로 부분수열 합이 32 이다.

지금까지 가장 큰 증가 부분수열의 합은 113 이다.

 

 

가장 큰 증가 부분수열 합은 113 이 된다.

 

 

 

 

🏆 배운 점

 

 

역시 비슷한 유형을 접하며 쉽게 해결한 문제이다.

 

많이 풀어보는 것이 힘이라는 것을 실감하게 된다.