백준 알고리즘, 11053, 11055 문제

---

---

풀이

DP 문제를 풀어가면서 가장 중요하다고 느낀 점은

"DP 배열을 어떻게 표현할 것인가" 이다.

지금까지의 DP 문제들은 "DP[x] = 문제에서 요구하는 x 의 결과값"  이었다.

즉 최종적으로 구하고 싶은 값이 x 이어도

DP 배열은 DP[x - y] 에 대하여 해당 x - y 에서의 문제가 요구하는 결과값을 담고 있도록 구성하였다.

그러나 이 문제들은 다르다.

DP 배열은 각각 대응되는 결과값으로 초기화 시킨다.

즉, 가장 긴 부분수열 문제의 경우에

10 20 10 30 20 50 의 입력값에 대하여

DP 배열은 idx 1 ~ 7 까지 모두 1 로 초기화 되고 

만약 조건을 통과하지 못하면

최종적으로 그대로 1 로 남는다.

이건 아주 큰 차이인데, 좀더 자세히 다음을 보면서 설명해보겠다.

10 20 10 의 입력이 있다고 하자.

DP[1] = 1

DP[2] = 2

DP[3] = 2

로 나와야 우리가 평소에 DP 배열을 만들던 방식이다.

그러나 이 문제에서는 

DP[1] = 1

DP[2] = 2

DP[3] = 1

로 남아있다.

최종 출력은 DP 배열 중, max 값을 찾아 출력한다.

물론 DP 배열에 모든 값에 대한 올바른 결과값을 담을 수 있는 방법도 있다.

그러나 문제마다 유연하게 DP 배열을 구성하는 능력을 갖출 필요성이 있어보인다.

---

코드

#11053 문제, @github 에서 보기

/**
 * @site: https://www.acmicpc.net/problem/11053
 * @github: https://github.com/7772
 * @auth: Landon Park
 * @date: 2018. 08. 02
 */
#include <iostream>
using namespace std;
int main() {
    int DP[1001];
    int arr[1001] = { 0, };
    int T;
    int i, j;
    int max = 1;
    cin >> T;
    for ( i = 1; i <= T; i++) cin >> arr[i];
    for (i = 1; i <= T; i++) {
        DP[i] = 1;
        for (j = 1; j < i; j++) {
            if (arr[i] > arr[j]) {
                // sum += arr[j];
                /**
                 * 이전 알고리즘들과 다른 점.
                 * 
                 * DP 배열은 해당 idx 에서 결과값을 나타냈었지만
                 * 이 알고리즘은 DP 배열이 해당 idx 에서 
                 * 매번 결과값을 나타내는 것이 아니다.
                 * 만약 새로 검사하는 값이 이전 배열의 idx 들 보다 크지 않다면
                 * 해당 idx 에서의 DP 배열은 1 로 고정된다.
                 */
                if (DP[i] <= DP[j] + 1) {
                    DP[i] = DP[j] + 1;
                    if (max < DP[i]) {
                        max = DP[i];
                    }
                }
            }
        }
    }
    cout << max << endl;
    // for (i = 1; i <= T; i++) cout << DP[i] << " " << endl;
    return 0;
}

#11055 문제, @github 에서 보기

/**
 * @site: https://www.acmicpc.net/problem/11055
 * @github: https://github.com/7772
 * @auth: Landon Park
 * @date: 2018. 08. 02
 */
#include <iostream>
using namespace std;
int main() {
    int DP[1001];
    int arr[1001] = { 0, };
    int T;
    int i, j;
    int max;
    cin >> T;
    for ( i = 1; i <= T; i++) cin >> arr[i];
    max = arr[1];
    for (i = 1; i <= T; i++) {
        DP[i] = arr[i];
        for (j = 1; j < i; j++) {
            if (arr[i] > arr[j]) {
                if (DP[i] <= DP[j] + arr[i]) {
                    DP[i] = DP[j] + arr[i];
                    if (max < DP[i]) {
                        max = DP[i];
                    }
                }
            }
        }
    }
    cout << max << endl;
    return 0;
}