Azza's Blog

이 문제는 다음과 같은 아이디어로 풀 수 있다.

기존의 식에 O[k-1] Operation과 B[k] Boolean 값이 추가 된 경우,

1. B[k-1] 까지 Evaluation 결과가 T인 경우와 F인 경우

2. B[k-2] 까지 Evaluation 결과가 T인 경우와 F인 경우

위의 경우에 따라, 나눠서 생각하면 된다.

점화식은 정리해 둔게 없어서 패스.

굳이 점화식 없어도 이런 문제들은 힌트 하나로 풀리는 거니깐.

실제 소스코드 부분은 다음과 같다.

void do_cbp() {
    int i, j;

    for(j = 0; j < MAX_OPER_COUNT+1; j++) {
        for(i = 0; i <= j; i++) {
            if(i == j) {
                DP[i][j] = (B[i] == T)? 1 : 0;
            } else if(i+1 == j) {
                DP[i][j] = Eval(B[j-1], O[j-1], B[j]);
            }
            else {  // if (j > i)
                Symbols eval = Eval(B[j-1], O[j-1], B[j])? T : F;

                DP[i][j] = DP[i][j-1] * Eval(T, O[j-1], B[j])
                        + (2^(j-i-2)-DP[i][j-1]) * Eval(F, O[j-1], B[j])
                        + DP[i][j-2] * Eval(T, O[j-2], eval)
                        + (2^(j-i-3)-DP[i][j-2]) * Eval(F, O[j-2], eval);
            }
        }

    }
}

이 문제는 종이에 점화식을 잘 적어둬서 간만에 점화식을 적을 수 있겠다.

점화식은 다음과 같다.

DP[[i][j] : i 번째 ~ j 번째 동전이 있을 때, Max Value.

N[k] : k 번째 동전의 금액.

( j == i+1 인 경우 )

DP[i][j] = Max(N[i], N[j])

( j > i+1 인 경우 )

Case_I = Max(DP[i+2][j], DP[i+1][j-1]) + N[i]        ; 내가 i 번째 동전을 택한 경우, 상대방의 선택 경우 중 Max 값 

Case_J = Max(DP[i+1][j-1], DP[i][j-2]) + N[j]        ; 내가 j 번째 동전을 택한 경우, 상대방의 선택 경우 중 Max 값

DP[i][j] = Max(Case_I, Case_J)

값을 구하는 순서는 [i][j] 에서

for(j = 0; j < k+1; k++)

for(i = j-1; i >= 0; i -= 2)

위의 순서로 구해야 한다. 물론 j 의 순서에 따라 i 의 순서가 바뀔 수도 있다.

소스코드는 아래와 같다.

void do_coingame() {
    int i, j;
    int case_i, case_j;

    for(j = 1; j < MAX_COINS; j++) {
        for(i = j-1; i >= 0; i -= 2) {
            if(j == i+1) {
                DP[i][j] = max(N[i], N[j]);
            } else {    // j > i+1, j will be j >= 2
                case_i = N[i] + max(DP[i+2][j], DP[i+1][j-1]);
                case_j = N[j] + max(DP[i+1][j-1], DP[i][j-2]);
                DP[i][j] = max(case_i, case_j);
            }
        }
    }
}

이 문제는 다음과 같은 아이디어로 풀었다.

DP[i] : i 번째 도시의 다리를 연결했을 때, 최대 다리 갯수.

DP[i] = DP[0]...DP[i-1] 에서 i 번째 다리를 연결 했을 때, Cross 되지 않는 경우 중 MAX 값 + 1

딱히 점화식을 쓰기도 복잡할 꺼 같아서 패스. 핵심 소스코드로 대신 함.

class Bridge {
public:
    int nc;
    int sc;

    bool isCross(const Bridge b) const {
        return ((b.nc-nc) * (b.sc-sc) > 0) ? false : true;
    }
};

bool check_cross(int bridge, int bridge_set) {
    int prev = bridge_set;

    while(prev > -1) {
        if(B[bridge].isCross(B[prev]))
            return true;
        prev = PREV[prev];
    }

    return false;
}

void do_bb() {
    int i, j, max_bridge;

    DP[0] = 1;
    PREV[0] = -1;
    max_bridge_idx = 0;
    for(i = 1; i < NUM_OF_CITIES; i++) {
        DP[i] = 0;
        PREV[i] = -1;    // i 번째 다리를 연결했을 때의 Bridge Set 을 구하기 위한 배열
        max_bridge = 0;
        for(j = 0; j < i; j++) {
            if(DP[j] > DP[i] && check_cross(i, j) == false) {
                DP[i] = DP[j];
                PREV[i] = j;
            }
        }
        DP[i]++;

        if(DP[i] > DP[max_bridge_idx])
            max_bridge_idx = i;
    }

}

해답을 얼핏 봤을 때, Knapsack 이라는 단어를 보고 아하! 했다.

정말 그 한 단어에 실마리가 풀릴줄이야. 그래서 내가 못 풀었다는 것이다.

문제를 푼 아이디어는 다음과 같다.

SUM[i] : i 번째 원소까지의 합이라고 했을 때,

SUM[i]/2  의 Capacity 를 가지는 Knapsack 에 들어가는 값을 구하면 되는 것이다.

점화식 쓰기도 고역이라 역시 패스하고 소스코드로 대신...

void do_bp() {

    int n, c;

    for(n = 0; n < NUMBERS; n++) {

        DP[n][0] = 0;

        for(c = 1; c <= HALF_SUM; c++) {

            if(c >= N[n]) {

                if(n >= 1) {

                    DP[n][c] = max(DP[n-1][c], DP[n-1][c-N[n]]+N[n]);

                } else {

                    DP[n][c] = N[n];

                }

            } else {

                if(n >= 1) {

                    DP[n][c] = DP[n-1][c];

                } else {

                    DP[n][c] = 0;

                }

            }

        }

    }

}

최장 길이와 수열을 모두 구하는 아이디어는 다음과 같다.

A[] - 집합 A

DP[j] : 0 ~ j th 까지의 LIS 값.

DP[j] 는 A[0] ~ A[j-1] 중 A[j] 보다 작으면서,

DP[] 값이 가장 긴 원소를 찾아 연결하면 된다.

DP[0] = 1

DP[j] = MAX(DP[k] + 1)        // 단 k = 0 ... j-1, A[j] > A[k] 인 경우

P[j] : j th Element 가 속한 LIS 에서 이전 Element 를 가리키는 Index

위와 같은 아이디어로 풀면 O(n^2) 복잡도가 나온다.

위키피디아에는 O(n log n) 으로 개선이 가능하다는데, 귀찮아서 패스.

void find_lis() {
    int i, j, prev;

    // Simple way
    for(i = 0; i < NUM_OF_NUMBERS; i++) {
        prev = -1;
        DP[i] = 0;
        DP_PREV[i] = -1;
        for(j = i-1; j >= 0; j--) {
            if(A[i] > A[j] && DP[j] > DP[prev])
                prev = j;
        }
        if(prev == -1)
            DP[i] = 1;
        else
            DP[i] = DP[prev] + 1;
        DP_PREV[i] = prev;
    }

}

아이디어는 다음과 같다.

1. Box 타입을 재구성.

   Box 는 Rotation 이 가능하므로,

   Box 의 H, W, D 가 각각 H 가 되는 경우로 나눔. 단, 재구성한 타입에서는 W > D 가 되도록 함.

2. 재구성한 Box 타입을 Sort. (큰 박스가 먼저 오도록.)

3. 위의 LIS 아이디어를 적용하여 문제 해결.

void box_stacking() {

    int i, j, total_max, max_height;

    DP[0] = B2[0].h;

    PREV[0] = -1;

    total_max = 0;

    for(i = 1; i < (int)B2.size(); i++) {

        DP[i] = B2[i].h;

        PREV[i] = -1;

        max_height = 0;

        for(j = 0; j < i; j++) {

            if(B2[j].canStack(B2[i]) && DP[j] > max_height) {

                DP[i] = DP[j] + B2[i].h;

                PREV[i] = j;

                max_height = DP[j];

            }

        }

        if(DP[i] > total_max)

            total_max = DP[i];

    }

}