[백준]_11055번 : 가장 큰 증가하는 부분 수열(파이썬 and C언어)

11055번: 가장 큰 증가하는 부분 수열

처음에 진짜 어떻게 접근해야 될지 하나도 몰라서 쩔쩔맸던 문제이다. 결국 질문 게시판에 들어가서 힌트를 조금 얻으려고 했는데 모든 질문들이 하나 같이 dp 리스트를 선언한 것을 알게 되었다. 사실 나는 dp(동적 계획법:dynamic programming) 문제인지도 모르고 문제에 덤볐던 것이다;; 잠시 문제를 접어두고 나서 dp를 조금 공부한 다음에 문제를 풀어 보기 시작했다. 당연히 풀릴 리가 없다ㅋㅋ. 그래서 구글에 올라와 있는 여러 풀이들을 보고 공부하면서 내 것으로 만드려고 최대한 노력하는 방법을 선택했다. 

---

접근

동적 계획법(다이나믹 프로그래밍)은 어떤 문제가 여러 개의 하위 문제로 나뉠 수 있을 때 하위 문제들의 결과를 저장하고 나중에 상위 문제의 결과를 도출할 때 하위 문제들의 결과를 바로 참고할 수 있게 하여 문제를 푸는 방법이다. 이번 문제에서도 이런 특징을 발견할 수 있다. 합이 가장 큰 증가 수열을 찾아야 하는 큰 문제를 하위 문제로 쪼개면 특정 위치의 원소까지 가능한 증가수열의 합을 수시로 계산하는 것이다. 이해를 돕기 위해 아래의 예를 살펴보자.

 

arr = { 1, 100, 2, 50, 60, 3, 5, 6, 7, 8 } # 입력받은 배열(불변)

dp = { 1, 100, 2, 50, 60, 3, 5, 6, 7, 8 } # 답으로 사용할 배열(가변)

위의 수열을 가지고 하위 문제를 풀어보자. 

먼저 100을 기준으로 검사를 진행하자. 1부터 진행하지 않는 이유는 1 앞의 원소가 없기 때문이다. 100 보다 앞에 있는 원소 1은 100보다 작기 때문에 dp[1]에 100 대신 1+100인 101을 대입해 준다.

 

101이 갖는 의미는 arr에서 i 인덱스부터 i-1 인덱스까지 검사했을 때 증가하는 부분들만 더해서 dp에 따로 저장해 놓는 것이다. 이것이 왜 중요하냐면 i 인덱스 이후로 다시 검사를 이어 나갈 때 그 이전 dp 값들이 누적되어 사용되기 때문이다.

 

따라서 dp는 아래와 같이 바뀐다.

dp = { 1, 101, 2, 50, 60, 3, 5, 6, 7, 8 }

 

이번에는 2를 기준으로 해보자. 1은 2보다 작기 때문에 dp[2]에 3(1+2)을 대입해 준다. 그다음으로 100은 2보다 작기 때문에 무시한다. 

 

따라서 dp는 아래와 같이 바뀐다.

dp = { 1, 101, 3, 50, 60, 3, 5, 6, 7, 8 }

 

다들 이제 어떤 방식인지 눈치챘을 것이다. 50을 기준으로 하면 다음과 같이 바뀐다.

dp = { 1, 101, 2, 53, 60, 3, 5, 6, 7, 8 }

 

그 이후로도 계속해준다. 조심할 점은 더할지 말지의 근거는 arr 에 근거한다. dp 는 연산의 결과일 뿐이다.

arr = { 1, 100, 2, 50, 60, 3, 5, 6, 7, 8 }

 

기준 : 60 → dp = { 1, 101, 2, 53, 113, 3, 5, 6, 7, 8 }

기준 : 3 → dp = { 1, 101, 2, 53, 113, 6, 5, 6, 7, 8 }

기준 : 5 → dp = { 1, 101, 2, 53, 113, 6, 11, 6, 7, 8 }

기준 : 6 → dp = { 1, 101, 2, 53, 113, 6, 11, 17, 7, 8 }

기준 : 7 → dp = { 1, 101, 2, 53, 113, 6, 11, 17, 24, 8 }

기준 : 8 → dp = { 1, 101, 2, 53, 113, 6, 11, 17, 24, 32 } 

 

즉 답이 113인 것을 알 수 있다. 이제 이것을 코드로 옮겨보자.  

시도 1(Python)

import sys
input=sys.stdin.readline
num=int(input())
dp=[*map(int, input().split())]
arr=dp[:]
for i in range(num):
    for j in range(i):
        if arr[j]<arr[i] and dp[i]<dp[j]+arr[i]:
            dp[i]=dp[j]+arr[i]
print(max(dp))

아마도 가장 이해가 안 가는 부분은 if 문의 조건들일 것이다. arr[j]<arr[i] and dp[i]<dp[j]+arr[i] 이 원소들의 연속적인 증가에 대한 합을 보장해 주는가? 코드를 하나씩 살펴보자. 

 

arr [j]<arr [i]  : 기준 원소(arr [i])보다 비교 원소(arr [j])가 작은지만 일단 확인

dp [i]<dp [j]+arr [i] : j 인덱스까지 쌓인 누적합(dp [j])에다가 arr [i]를 더한 값이 dp [i]보다 크면 dp [i]를 dp [j]+arr [i]로 갱신해 준다. 

 

첫 번째 조건만 보면 흠이 있다. arr [j]가 arr [i]보다 작다고 해서 연속적인 증가라는 보장이 없지 않은가?!!!. 정확하다! 틀리지 않았기 때문에 두 번째 조건이 and로 붙어 있는 것이다. 예를 들어 arr={ 1, 2, 4, 3, 5 }를 확인해야 되고 5가 i 인덱스고 4가 j 인덱스면 일단 dp={ 1, 3, 7, 6, 12 }이다. 이제 j 인덱스를 3으로 옮겨보자. 하지만 이때 첫 번째 조건은 만족하지만 두 번째 조건을 만족하지 못한다(12 <6+5). 따라서 두 번째 조건이 알아서 dp에 대입될 원소들이 연속적인 증가들인지 걸러주는 역할을 하는 것이다.

 

시도 2(C언어)

#include <stdio.h>
#include <stdlib.h>
int descending(const void* a, const void* b) {
    int A = *(int*)a;
    int B = *(int*)b;
    return B-A;
}

int main() {
    int num;
    scanf("%d",&num);
    int* arr=(int*)malloc(num * sizeof(int));
    int* dp=(int*)malloc(num * sizeof(int));
    for(int i=0;i<num;i++){
        scanf("%d",&arr[i]);
        dp[i]=arr[i];
    }
    for(int i=0;i<num;i++)
        for(int j=0;j<i;j++){
            if(arr[j]<arr[i] && dp[i]<dp[j]+arr[i]) dp[i]=dp[j]+arr[i];
        }
    qsort(dp, num, sizeof(int), descending);
    printf("%d",*dp);
    free(dp);
    return 0;
}