Dynamic Programming - Counting Boolean Parenthesizations, Optimal Strategy for a Game

- Counting Boolean Parenthesizations

문제) 5개의 심볼을 가지고 만든 Boolean Expression을 괄호로 묶어 Evaluation했을 때,

        결과가 true 가 되는 Case 의 갯수는 몇 개인가?

        심볼 = { true, false, and, or, xor }

        예를 들면, ' false and true xor true '가 true 가 되는 괄호 묶기 방법은 1가지 밖에 없다.

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

기존의 식에 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);
            }
        }

    }
}

- Optimal Strategy for a Game

문제) N 개의 동전이 있다. (N은 항상 짝수)

        각 동전의 가치는 V(0)...V(N)이며, 이 동전들은 일렬로 놓여져 있다.

        두 사람이 일렬로 놓여져 있는 동전의 양쪽 끝 동전 중 하나를 가질 수 있다고 할 때,

        처음 시작하는 사람이 가능한 최대 금액은 얼마인가?

       상대방이 무엇을 선택하는지는 여기에서 문제가 아니다.

       모든 경우의 수에서 최대값을 찾는 문제인 것이다.

       처음엔 "상대방은?" 이라는 생각에 잠시 혼란스러웠었다.

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

점화식은 다음과 같다.

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

두 문제 다, 나름 풀만한 문제였다.

근데, 이 두 문제 전에 있는 문제인 Edit Distance는 당췌 아이디어가 안 떠오르네...