Dynamic Programming - Building Bridges, Balanced Partition.

1) Building Bridges

문제내용:

가운데로 강이 지나가는 2차원 지도가 있다. 강 북쪽과 남쪽으로 각각 N 개의 도시가 있다.

이 N 개의 도시를 A(1)...A(N), B(1)...B(N) 이라고 한다.

이 도시는 순서대로 위치해 있지는 않다. (즉 A(1) 옆에 A(2) 가 있는게 아니라는 말)

강 북쪽과 남쪽은 연결하는 다리를 건설하고자 하는데,

다리의 건설은 A(k) 와 B(k) 만 연결할 수 있다.

이 때, 가장 다리를 많이 놓을 수 있는 갯수는 몇 개 인가?

설명이 은근히 길다.

그림으로 그리고 싶지만, 잘 찾지도 못하겠고 그리기도 귀찮아서 패스.

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

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;
    }

}

- Balanced Partition

문제:

N 개의 정수를 가진 집합을 2개의 Subset S1, S2 로 나누었을 때, |Sum(S1) - Sum(S2)| 의 최소값을 구하라.

사실 이 문제는 내가 못 풀었다.

Subset 을 나누는 데, 단순히 한 Element 를 기준으로 좌/우로 나누는 건줄 알았다.

그래서 문제를 이해해서 제대로 못 풀었다.

그리고 해답을 얼핏 보고 아하.. 하고 다시 푼 문제.

해답을 얼핏 봤을 때, 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;

                }

            }

        }

    }

}