[백준 BOJ] 14756. Telescope

난이도

Platinum I

문제 풀이

2017 ICPC 인터넷 예선 문제다. 문제는 간단하다. Telescope를 왼쪽에서 오른쪽으로 훑으면서 구한 값이 W보다 큰 횟수가 몇 번인지를 구하면 된다. 아주 친절하게 무슨 수식으로 구하는 지도 알려준다.

각 위치 \(\scriptsize k\)에서 \(\scriptsize W_k\)는 다음과 같은 식으로 구할 수 있다.

\[W_k = \sum_{i = 0}^{M - 1}\sum_{j = 0}^{L - 1}T(i, j + k)P(i, j)\]

각 행에서 어떤 값을 구하는 지를 한 번 살펴보자. 대충 \(\scriptsize i = 0\)이라고 하고 관찰해보자.

\[W_{k0} = \sum_{j = 0}^{L - 1}T(0, j + k)P(0, j)\]

즉, 각 위치에서 M개의 행에 대해 해당 값을 계산해주면 된다. 단순 곱셈을 하는 문제로 생각할 수 있다. 제한이 \(\scriptsize l = 10000, n = 3000, m = 100\)이므로, 나이브하게 곱셈을 연산해 값을 얻어오기엔 무리가 있다는 것을 쉽게 알 수 있다.

따라서, 곱셈을 빠르게 하는 방법을 생각해보면 되고 그 방법으로 FFT를 떠올릴 수 있다.

컨볼루션 꼴로 고치기 위해서 \(\scriptsize P\)의 순서가 반대로 되어있는 행렬 \(\scriptsize P'\)을 한 번 생각해보자. 그럼 위의 식은 다음과 같은 꼴로 고칠 수 있다.

\[W_{k0} = \sum_{x + y = k + L - 1}T(0, x)P'(0, y)\]

누가봐도 FFT 해달라는 꼴이기 때문에 하면 된다. \(\scriptsize L - 1\) 부터 \(\scriptsize N - 1\)까지 계수가 필요하니 구해주면 되고, 이를 \(\scriptsize M = 1\)부터 \(\scriptsize 100\)(각 행 별로 FFT)까지 FFT를 통해 얻어내서 한 곳에 더해 값을 가지고 있으면 된다.

    ll N, I, M, W; cin >> N >> I >> M >> W;
    vector<vector<cpx>> T(M, vector<cpx>(N));
    vector<vector<cpx>> P(M, vector<cpx>(N));

    for(int i = 0; i < M; ++i) {
        for(int j = 0; j < N; ++j) {
            int x; cin >> x;
            T[i][j] = cpx(x, 0);
        }
    }

    for(int i = 0; i < M; ++i) {
        for(int j = 0; j < I; ++j) {
            int x; cin >> x;
            P[i][I - 1 - j] = cpx(x, 0);
        }
    }

    vector<ll> total_w(N);
    for(ll i = 0; i < M; ++i) {
        vector<cpx> w_i = solve(T[i], P[i]);
        for(int j = I - 1; j <= N - 1; ++j) {
            total_w[j] += (ll)w_i[j].real();
        }
    }

(코드에서 solve가 컨볼루션 구해주는 함수)

이후 더한 값이 \(\scriptsize W\)보다 큰 지 비교해서 답을 구해주면 된다.

    ll cnt = 0;
    for(ll i = I - 1; i <= N - 1; ++i) {
        if(total_w[i] > W) cnt++;
    }

    cout << cnt << '\n';

주의 : \(\scriptsize W\)는 long long 범위다.. 내가 이걸 캐치못해서 맞왜틀을 엄청나게 하다가.. ingyu1008씨가 알려줘서 맞췄다 ㅠㅜㅠ

코드 전문

14756 // Telescope