Azza's Blog

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

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;

                }

            }

        }

    }

}