[ 백준 ] 5525 / IOIOI

7919 단어 psbojboj

# Appreciation

/*
 * Problem :: 5525 / IOIOI
 *
 * Kind :: Dynamic Programming
 *
 * Insight
 * - 한번 문자열 검사 : N
 *   필요한 최소 검사 횟수 : M-N+1 => N+2 (M >= 2N+1)
 *   O(N^2) = O(10^12) > O(10^8) => 시간 초과
 *   + 즉,
 *   for (int i=0; i<=M-N; i++) {
 *       if (P_N == p.substr(i, 2*N+1)) {
 *           ans++;
 *       }
 *   }
 *   이렇게 앞에서 부터 일치하는지 일일이 검사하고 있으면 시간초과가 날 수밖에 없다
 *
 * - P_1 : IOI
 *   P_2 : IOIOI
 *   P_3 : IOIOIOI
 *   ...
 *   + OOIOIOIOI 라는 문자열이 있고 IOIOIOI (P_3) 가 몇 번 포함되어있는지 알고 싶다고 하자
 *     앞에서부터 문자열을 차례대로 읽다 보면 OOIOIOI 를 읽는 순간이 존재한다
 *     이제 OOIOIOIOI 를 읽는 순간이 왔다고 하면,
 *     그 전에 OOIOIOI 읽었던 순간에 얻을 수 있는 정보를 활용해서
 *     유의미한 정보(P_3 발견)를 얻어낼 수 있나?
 *     # OOIOIOI 까지 읽었을 때, 읽었던 문자열에서
 *       마지막 문자를 끝으로 하는 P_2 이 발견되었음을 안다면,
 *       OOIOIOIOI 까지 읽었을 때, P_3 가 발견되었음 쉽게 알 수 있지 않을까?
 *       -> dp[i] = i 번째 문자를 끝으로 하는 P_N 이 있을 때, N 의 최댓값
 *          이라고 정의하면,
 *               OOIOIOI
 *          dp : 0000102 - P_2 발견
 *               OOIOIOIOI
 *          dp : 000010203 - P_3 발견
 *       -> 즉, i 번째를 문자를 보고 있을 때
 *          i 번째 문자 == 'I', i-1 번째 문자 == 'O', i-2 번째 문자 == 'I' 라면,
 *          일단 P_1 임을 알 수 있다
 *          그런데 dp[i-2] 가 2 라면, i-2 번째 이전의 문자들을 검사하지 않고도
 *          그 문자를 끝으로 하는 P_N 에서 P_2 이 최대임을 알 수 있다
 *          따라서, dp[i] = dp[i-2] + 1 => 3 임을 알 수 있고
 *          이는 i 번째 문자를 끝으로 하는 P_N 이 있을 때, P_3 가 최대라는 것이다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    int M; cin >> M;
    string S; cin >> S;

    // Process
    int dp[M]; /* dp[i] = i 번째 문자를 끝으로 하는 P_N 에서 N 의 최댓값
                * P_0 을 "I" || "O" 로 가정함
                * 즉, dp[i] = 0 이라면, P_N (N >=1) 이 존재하지 않음을 가리킴 */
    memset(dp, 0, sizeof(dp));
    int ans = 0;
    for (int i=2; i<M; i++) {
        /* 문자열 : .........IOI
         * 인덱스 : 0123.......i 라면 */
        if (S[i] == 'I' && S[i-1] == 'O' && S[i-2] == 'I') {
            /* dp[i-2] = N 이라면 "OI" 가 뒤에 붙어 dp[i] = N+1 이 됨
             * 즉, P_N + "OI" => P_(N+1) 이 된 것을 뜻함 */
            dp[i] = dp[i-2] + 1;
            /* dp[i] = N 이면
             * i 번째 문자를 끝으로 하는 P_0, P_1, ... , P_N 이 새로 발견된 것을 뜻하며
             * 따라서, dp[i] >= N 이면 새로운 P_N 이 발견되었으므로 세어줌 */
            if (dp[i] >= N) {
                ans++;
            }
        }
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
/* None */

좋은 웹페이지 즐겨찾기