OCR (상, p. 285)

2025년 10월 30일

어떻게 풀었나?#

처음으로 풀어본 ‘상’ 난이도 문제

책의 앞부분에 FANMEETING이라는 분할정복 ‘상’ 난이도 문제가 있었는데, 2025년 10월 30일 기준으로 아직 미해결이라 실제로 AC까지 받아본 난이도 ‘상’ 문제는 이게 처음.

맨 처음에는 어떻게 접근해야 할지, 정확히 어떤 확률을 구해야 하는지 모르는 상태였음.

감을 전혀 못잡고 있다가 어쨌든 확률이 최대가 되는 케이스를 구하는 거라 생각하고 끄적여 봤는데, T[i][x]가 words[i]다음에 words[x]가 올 확률이라 했으므로, 이전 단어와 이후 단어의 관계를 따져봐야 할 것 같다는 생각이 듦.

그래서 n-1번째까지는 words[i]를 썼는데 n번째 단어로 words[x]를 고르게 되는 경우의 확률을 따져보고, 그런 관계를 점화식으로 표현할 수 있는지 생각해봄.

점화식 자체는 아래와 같이 금방 나왔음.

$f(n,x) = f(n-1,i)\times T[i][x] \times M[x][result[n]]$

(※ Classifier가 n번째 단어로 words[idx]를 택했을 때, idx를 result[n]으로 표현함)

즉, n번째 단어가 words[x]로 끝나는 최대 확률( $f(n,x)$ )은 n-1번째 단어가 words[i]로 끝나는 확률 ( $f(n-1,i)$ )과 words[i]이후에 words[x]가 나오는 확률( $T[i][x]$ )을 곱하고, n번째 단어를 Classifier가 words[x]인데 words[result[n]]으로 판독할 확률( $M[x][result[n]]$ )을 곱한 값임.

Base Case는 $B[x]\times M[x][result[n]]$으로 나타낼 수 있었음.

참고로 words[] 배열을 0부터 m-1까지 쓰고, words[m]을 “마지막 노드”를 의미하는 값으로 생각하면 코드 구현하기가 쉬움.

그 이후 이것을 코드로 옮겨서 제출했는데, WA

책을 보니 이런 소수 값들을 계속 곱해나가면, 그 값이 너무 작아져서 문제가 되니 log로 표현해야 한다 했음.

log로 변경하니 AC 받을 수 있었음.

문제#

정답 코드#

#include <bits/stdc++.h>
using namespace std;
string words[501];
double B[501], T[501][501], M[501][501];
unordered_map<string, int> udic;
int result[101]; // result[n]: 분류기가 분류한 결과에서 n번째 단어로 분류된 words 배열의 index

int m;
int CHKVAL;
int chk[101][501];
double dp[101][501];
int ans[101][501];

void GetAns(int n, int x) {
    if(n==0) return;
    int prv_x = ans[n][x];
    GetAns(n-1, prv_x);
    printf("%s ", words[prv_x].c_str());
}

double f(int n, int x) { //f(n,x) = log(n번째 단어가 words[x]로 끝나는 최대 확률)
    if(n == 0) {
        return B[x] + M[x][result[n]];
    }
    double& ret = dp[n][x];
    if(chk[n][x] == CHKVAL) return ret;
    chk[n][x] = CHKVAL;

    ret = log(0.0); //-inf
    double tmp;
    ans[n][x] = -1;
    for(int i = 0; i < m; i++) {
        tmp = f(n-1, i) + T[i][x] + M[x][result[n]];
        //T[i][x] = log(words[i]다음에 words[x]가 올 확률)
        //M[x][result[n]] = log(words[x]를 words[result[n]]으로 판독할 확률률
        if(ret < tmp) {
            ret = tmp;
            ans[n][x] = i;
        }
    }
    return ret;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int q;
    cin >> m >> q;
    for(int i = 0; i < m; i++) {
        cin >> words[i];
        udic[words[i]] = i;
    }
    //words[m]은 '끝'을 의미하도록 설정

    double val;
    for(int i = 0; i < m; i++) {
        cin >> val;
        B[i] = log(val);
    }
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < m; j++) {
            cin >> val;
            T[i][j] = log(val);
        }
        T[i][m]=log(1.0); //모든 단어에서 끝날 수 있음을 표현.
    }
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < m; j++) {
            cin >> val;
            M[i][j] = log(val);
        }
    }
    M[m][m]=log(1.0);

    string qword;
    for(int i = 0; i < q; i++) {
        CHKVAL++;
        int n; cin >> n;
        for(int j = 0; j < n; j++) {
            cin >> qword;
            result[j] = udic[qword];
        }
        result[n] = m;

        f(n,m);
        GetAns(n, m);
        puts("");
    }
    return 0;
}

난이도 ‘상’에 걸맞는 문제였다.