240429: 클래스 3의 8문제 풀이. 방문 체크는 큐를 넣을 때 ⚠️

2024-04-29

CLASS 3 풀이

어제 오늘, Solved.ac 클래스 3의 문제 8개를 풀었다

• 연결 요소의 개수 (실버 2 - 11724)
• Z (실버 1 - 1074)
• 쉬운 최단거리 (실버 1 - 14940)
• 패션왕 신해빈 (실버 3 - 9375)
• Four Squares (실버 3 - 17626)
• 헌내기는 친구가 필요해 (실버 2 - 21736)
• 케빈 베이컨의 6단계 법칙 (실버 1 - 1389)
• IOIOI (실버 1 - 5525)

CLASS 3 금장까지 앞으로 9문제 남았다.

BFS에서 큐를 넣을 때 방문체크 하는 것이 더 효율적이다.

오늘의 제일 큰 깨달음. BFS 탐색에서, Queue를 뺄 때 방문체크를 하면 이전에 넣어놨던 밀려있는 Queue 때문에 불필요한 중복 검색이 일어날 수 있다. Queue를 넣을 때 방문체크 하는 것이 더 효율적이다.

---

연결 요소의 개수 (그래프 이론, 탐색)

기초 그래프 문제, 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하면 된다.

새로운 노드에서부터 탐색을 시작할때마다 카운트를 하면 된다. 만약 모든 노드가 서로 연결되어 있다면, 한번의 탐색 시작으로 모든 노드가 방문 체크가 될 것.

// 백준: 연결 요소의 개수
// https://www.acmicpc.net/problem/11724
// 2024-04-25

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
    int N, M; // 정점 N, 간선 M;
    cin >> N >> M;
    vector<vector<int>> adj(N + 1, vector<int>());
    vector<int> visited(N + 1, false);

    for (int i = 0; i < M; ++i) {
        int from, to;
        cin >> from >> to;
        adj[from].push_back(to);
        adj[to].push_back(from);
    }

    int count = 0;

    for (int i = 1; i <= N; ++i) {
        if (!visited[i]) {
            ++count;
            queue<int> q;
            q.push(i);
            visited[i] = true;

            while (!q.empty()) {
                int cur_node = q.front();
                q.pop();
                for (int next : adj[cur_node]) {
                    if (!visited[next]) {
                        visited[next] = true;
                        q.push(next);
                    }
                }
            }
        }
    }

    cout << count;

    return 0;
}

---

Z (분할 정복, 재귀)

크기가 2^N * 2^N인 2차원 배열을 Z모양으로 탐색한다. N이 주어졌을 때, r행 c열을 몇번째로 방문하는지 출력하시오.

Z 문제는 오랜만의 분할 정복(Divide and Conquer) 문제였다.
분할 정복 문제는 말 그대로 Divide and Conquer 하는 문제로 문제를 작은 문제로 분할 (Divide) 그리고 (And) 정복 (Conquer) 하는 문제다.

동적 계획법과는 다르다, 동적 계획법은 중복되는 하위 문제를 효율적으로 푸는 것이고, 분할 정복은 큰 문제를 작게 분할해서 정복하는 것.

아이디어는 다음과 같다.

맵을 1~4분면으로 나눈다고 하자 (인덱스 순으로 좌측 상단, 우측 상단, 좌측 하단, 우측 하단)
주어지는 r과 c가 n사분면에 있다면, 그 이전 사분면의 모든 칸을 더하고 해당 사분면만 계산하면 된다 (이전 사분면까지 계산할 필요가 없다!)

예를 들어서, r과 c가 2사분면에 속한다면 1사분면의 모든 칸 수를 더해놓고 2사분면부터 탐색을 시작하면 된다.

풀이

1. 입력 된 r, c 값이 현재 맵에서 몇 사분면인지 확인한다
2. 이전 사분면까지의 칸 수를 모두 더하고, 재귀로 r, c 값이 현재 있는 사분면을 또 4분할 하고 거기서 몇 사분면인지 확인한다
3. 반복

// 백준: Z
// https://www.acmicpc.net/problem/1074
// 2024-04-26

#include <iostream>
using namespace std;

int solve(int n, int r, int c) {
    // 기저 조건
    if (n == 0) {
        return 0;
    }
    int half = 1 << (n - 1); // n-1의 거듭 제곱 구하기 (절반)
    int size = half * half;  // 한 분면의 크기

    if (r < half && c < half) { // 왼쪽 상단
        return solve(n - 1, r, c);
    } else if (r < half && c >= half) { // 오른쪽 상단
        return size + solve(n - 1, r, c - half);
    } else if (r >= half && c < half) { // 왼쪽 하단
        return 2 * size + solve(n - 1, r - half, c);
    } else { // 오른쪽 하단
        return 3 * size + solve(n - 1, r - half, c - half);
    }
}

int main() {
    int N, r, c;
    cin >> N >> r >> c;
    cout << solve(N, r, c);
    return 0;
}

---

쉬운 최단거리 (그래프 이론, BFS)

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

이 문제는 단순한 최단 거리 문제지만, 약간 다르다.
시작 지점이 주어지지 않으며, 각 모든 지점에서 목표까지의 거리를 저장한 데이터 셋을 넘기는 문제.
BFS 특성상 제일 처음 도달한 루트가 최단 거리이므로, Queue를 이용해 BFS를 구현했다.

이 문제는 약간의 역발상이 필요하다.
주어진 모든 위치에 대해서 목표 지점까지의 거리를 BFS 브루트포스로 구하는 것은 너무 비효율적이다.
역으로 목표지점에서부터 가능한 모든 루트로 BFS를 통해 가면서 거리를 기록하면 된다.

// 백준: 쉬운 최단거리
// https://www.acmicpc.net/problem/14940
// 2024-04-27

/*
주어진 모든 위치에 대해서 목표 지점까지의 거리를 BFS 브루트포스로 구하는 것은 너무 비효율적이다.
역으로 목표지점에서부터 가능한 모든 루트로 BFS를 통해 가면서 거리를 기록하면 되지 않을까?
*/

#include <iostream>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

vector<vector<int>> map;
vector<vector<int>> distances;
int n, m;
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    map.assign(n, vector<int>(m));
    distances.assign(n, vector<int>(m, -1));
    pair<int, int> targetPos;

    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < m; ++c) {
            cin >> map[r][c];
            if (map[r][c] == 0)
                distances[r][c] = 0;
            else if (map[r][c] == 2)
                targetPos = {r, c};
        }
    }

    queue<pair<int, int>> q;
    q.push(targetPos);
    distances[targetPos.first][targetPos.second] = 0;

    while (!q.empty()) {
        int cur_r = q.front().first;
        int cur_c = q.front().second;
        q.pop();

        for (int i = 0; i < 4; ++i) {
            int next_r = cur_r + dr[i];
            int next_c = cur_c + dc[i];
            if (next_r >= 0 && next_c >= 0 && next_r < n && next_c < m && map[next_r][next_c] == 1 && distances[next_r][next_c] == -1) {
                distances[next_r][next_c] = distances[cur_r][cur_c] + 1;
                q.push({next_r, next_c});
            }
        }
    }

    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < m; ++c) {
            cout << distances[r][c] << " ";
        }
        cout << "\n";
    }

    return 0;
}

---

패션왕 신해빈 (해시를 사용한 집합과 맵)

해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?

프로그래머스 알고리즘 정복 킷에서도 본 문제같다. 이건 약간의 수학적 지식이 있어야 한다.
각 범주에서 가능한 모든 조합은 간단하게 곱하면 된다.

예를 들어서, 옷과 바지가 두벌 있다면 가능한 조합은 2*2로 총 4 조합이지만, 아무것도 입지 않는 상태를 고려해야 한다.

옷 1을 입었을 때, 옷 2를 입었을 때, 옷을 입지 않았을 때로 가능한 모든 상태는 각 범주에 대해 +1이다 (입지 않았을 때 고려)

따라서 옷과 바지가 두벌 있다면 가능한 조합은 3*3으로 9 조합이지만, 옷과 바지 둘 다 입지 않을 경우는 알몸이고, 알몸은 허용되지 않으므로 -1을 한다.

키-값 쌍을 저장하는 연관 컨테이너인 map을 이용해서, 각 범주의 옷의 개수를 효율적으로 관리한다음. 약간의 수학 식을 더해 풀 수 있는 문제였다.

map의 순서는 중요하지 않으므로 해시를 사용한 unordered_map 을 사용해서 효율성을 올렸다.

// 백준: 패션왕 신해빈
// https://www.acmicpc.net/problem/9375
// 2024-04-28

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

/*
1. 각 범주에서 가능한 선택지의 수를 모두 곱한다 (입지 않았을 때 포함)
2. 모두 입지 않는 (알몸) 상태는 불가하므로 -1 한다.
*/

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        unordered_map<string, int> map;
        for (int i = 0; i < N; ++i) {
            string type;
            cin.ignore(25, ' ');
            cin >> type;
            map[type]++;
        }

        int result = 1;
        for (auto it = map.begin(); it != map.end(); ++it) {
            result *= (it->second + 1);
        }

        cout << result - 1 << "\n";
    }
    return 0;
}

---

Four Squares (DP, BruteForce)

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 5^2과 1^2의 합이다; 또한 4^2 + 3^2 + 1^2으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 125^2 + 6^2 + 1^2 + 1^2라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 105^2 + 15^2 + 8^2 + 5^2.

자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.

이 문제는 조금 점화식 찾기 복잡한 DP 문제였다.
먼저 1. 중복되는 하위 문제를 찾고 / 2. 기본 사례를 식별했다.

dp[i]를 i를 만드는데 필요한 최소 제곱수의 합이라고 두고, 1부터 자연수 n까지 반복하면서, 자연수 n에 다른 제곱수의 최소 합을 더하면서 최솟값을 찾으면 된다.

즉, dp[i] = min(dp[i], dp[i - (j * j)] + 1); 하면 된다.
기본 사례를 설정해놓고 1부터 주어진 자연수 n까지 bottom-up 방식으로 (top-down과는 반대) 제곱수의 최소 합을 찾는다. n에 대해서 n을 만드는 제곱수 최소 합은 dp[i] = min(dp[i], dp[i - (j * j)] + 1); 이다.

    for (int i = 5; i <= N; ++i) {
        for (int j = 1; j * j <= i; ++j) {
            dp[i] = min(dp[i], dp[i - (j * j)] + 1);
        }
    }

이렇게 기본 사례를 4까지 설정하고, 5부터 Bottom-Up 방식으로 배열을 채워나갔다.

// 백준: Four Squares
// https://www.acmicpc.net/problem/17626
// 2024-04-28

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> dp(N + 1, 0);
    for (int i = 0; i <= N; ++i) {
        dp[i] = i;
    }

    // BASE CASE
    dp[0] = 0;
    if (N >= 1)
        dp[1] = 1;
    if (N >= 2)
        dp[2] = 2;
    if (N >= 3)
        dp[3] = 3;
    if (N >= 4)
        dp[4] = 1;

    for (int i = 5; i <= N; ++i) {
        for (int j = 1; j * j <= i; ++j) {
            dp[i] = min(dp[i], dp[i - (j * j)] + 1);
        }
    }

    cout << dp[N];
    return 0;
}

---

헌내기는 친구가 필요해 (그래프 이론, 탐색)

2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다. 

불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해보자.

둘째 줄부터 𝑁개의 줄에는 캠퍼스의 정보들이 주어진다. `O`는 빈 공간, `X`는 벽, `I`는 도연이, `P`는 사람이다. `I`가 한 번만 주어짐이 보장된다.

기본적은 그래프 탐색 문제, 최단 거리를 요구하지 않음으로 BFS / DFS 중 아무거나 사용해도 풀 수 있다.
여기서 중요한점은, 시간 제한이 빡빡함으로 방문 체크 시점에 유의해야한다. 방문 체크를 BFS에서 Queue를 뺄 때 하면, 이전에 밀려있는 Queue가 실행될때는 이미 그 큐가 방문이 되어있는 상태일 수 있다. 따라서 중복 체크가 일어나게 되고. 이는 비효율을 낳는다.

Queue를 넣을 때 방문 체크하자. 이래야 중복 체크를 막을 수 있다
정확하겐 방문 체크라기 보단, 방문 할거라고 '확인' 한. 출석 체크 느낌으로..

// 백준: 헌내기는 친구가 필요해
// https://www.acmicpc.net/problem/21736
// 2024-04-29

/*
큐에서 뺄 때 방문 체크 하는 것은 중복 방문이 일어날 수 있다.
큐에 넣을때 방문 체크 하는 것이 더 효율적이다.
*/

#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;

int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, M;
    cin >> N >> M;
    pair<int, int> startPos;
    vector<vector<char>> map(N + 1, vector<char>(M + 1)); // 방문 표시 겸용
    for (int r = 1; r <= N; ++r) {
        for (int c = 1; c <= M; ++c) {
            char next;
            cin >> next;
            map[r][c] = next;
            if (next == 'I')
                startPos = {r, c};
        }
    }
    int count = 0;
    queue<pair<int, int>> q;
    q.push({startPos.first, startPos.second});

    while (!q.empty()) {
        int cur_r = q.front().first;
        int cur_c = q.front().second;
        q.pop();

        for (int i = 0; i < 4; ++i) {
            int next_r = cur_r + dr[i];
            int next_c = cur_c + dc[i];
            if (next_r > 0 && next_c > 0 && next_r <= N && next_c <= M && map[next_r][next_c] != 'X') { // VALID CHECK
                if (map[next_r][next_c] == 'P')
                    count++;
                map[next_r][next_c] = 'X'; // 큐에 넣을 때 방문 표시
                q.push({next_r, next_c});
            }
        }
    }

    cout << (count != 0 ? to_string(count) : "TT");
    return 0;
}

---

케빈 베이컨의 6단계 법칙 (그래프 이론, 탐색)

케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?

천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.

케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.

오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.

1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6이다.

2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.

3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 통해 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 1+1+1+2 = 5이다.

4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다. 4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다.

마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다. 5의 케빈 베이컨의 수는 2+3+2+1 = 8이다.

5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.

BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

문제를 해석하자면, 각 노드에서부터 모든 노드까지 걸리는 최단 가중치의 누적합이 제일 작은 노드를 구하는 것.
문제만 읽으면 재밌지만, 전형적인 그래프 문제를 벗어나진 못했다.

// 백준: 케빈 베이컨의 6단계 법칙
// https://www.acmicpc.net/problem/1389
// 2024-04-29

/*
1. 이중 반복문으로 from -> to 지정
2. BFS로 from에서 부터 모든 to까지의 거리 구하기
*/

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; // 유저 수 N, 관계 수 M.
    cin >> N >> M;
    vector<vector<int>> adj(N + 1, vector<int>());
    for (int i = 0; i < M; ++i) {
        int from, to;
        cin >> from >> to;
        adj[from].push_back(to);
        adj[to].push_back(from);
    }

    int known_min_man = -1;
    int known_min_dist = (~0U >> 2);

    for (int from = 1; from <= N; ++from) { // 케빈 베이컨 조사 당할 사람
        int sum_dist = 0;
        for (int to = 1; to <= N; ++to) { // from -> to 거리 조사
            if (to == from)
                continue; // 자기자신 스킵

            // BFS 시작 (from -> to)
            queue<pair<int, int>> q; // node,  t
            vector<int> visited(N + 1, false);
            q.push({from, 0});
            visited[from] = true; // 시작 방문 체크
            while (!q.empty()) {
                int cur_node = q.front().first;
                int cur_time = q.front().second;
                q.pop();

                // 체크
                if (cur_node == to) {
                    sum_dist += cur_time; // 거리합에 가중치를 누적시키고
                    break;                // 종료
                }

                for (int &next : adj[cur_node]) {
                    if (!visited[next]) {
                        visited[next] = true; // 방문 표시
                        q.push({next, cur_time + 1});
                    }
                }
            }
        }

        // from에 대한 케빈 베이컨 조사 끝
        if (sum_dist < known_min_dist) {
            known_min_dist = sum_dist;
            known_min_man = from;
        }
    }

    cout << known_min_man;
    return 0;
}

---

IOIOI (문자열)

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.

P1 IOI
P2 IOIOI
P3 IOIOIOI
PN IOIOI...OI (O가 N개)
I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

이 문제는 I와 O로 이루어진 문자열이 주어질 때, 특정 패턴(IOI...) 가 몇번 출현하는지 알아내는 문제.

내가 좀 어렵게 풀었다, 문자열 파싱을 브루트포스로 하는데 여러가지 최적화를 해서 억지로 푼 느낌이다. 실행 시간은 8ms로 빨랐지만, 코드가 간결하진 못했다.

백준 스터디그룹에 계신 분이 다른 아이디어를 주셨는데, 이게 훨씬 간결하고 속도가 빠른 것 같다.

아이디어:

1. I O I O 연속 개수를 세다가
2. 끊겼을 때, 지금까지 세진 개수로 몇개의 Pn이 만들어지는지 확인
3. 반복

훨씬 간결하다. 내가 복잡하게 풀었다.

나는 모든 I에 대해 탐색을 시작하면서

1. 만약 유효한 문자열로 탐색이 완료 됐다면, 인덱스를 기록하고 다음 탐색 때 해당 인덱스까지 스킵하기 (여기까지 하니까 57%에서 TLE)
2. 문자열 탐색하다가 중간에 틀렸다면, 틀린 인덱스 기록하고 다음 탐색 때 해당 인덱스까진 탐색하지 않기

이렇게 두개의 최적화를 했고. 결국엔 8ms의 실행 시간으로 풀었다. (이전에 TLE를 3번정도 받았다)

확실히 연속 개수를 세고, 끊겼을 때 연속된 개수에서 나올 수 있는 패턴의 개수를 합하는 게 훨씬 간결하고 합리적이다.

// 백준: IOIOI
// https://www.acmicpc.net/problem/5525
// 2024-04-29

#include <iostream>
#include <string>
using namespace std;

int N, M;
string S;
int pattern_len;
int prev_complete_index = -1; // 탐색 완료한 인덱스 표시 (최적화)
int problem_index = -1;       // 문제 발생한 인덱스 표시 (최적화)

bool check(int start_index) {
    int end_index = start_index + pattern_len; // start_index부터 end_index 미만까지 loop
    if (start_index < prev_complete_index) {   // 시작 인덱스가 이미 탐색 되었다면
        start_index = prev_complete_index - 1; // 탐색이 끝난곳부터 탐색
    }

    if (end_index > M)
        return false; // 범위 초과

    /*
    탐색이 끝난 곳 (prev_complete_index)나, 탐색을 시작한 곳 (check() 호출)의 인덱스는
    무조건 'I' 부터 시작한다고 확신할 수 있다.
    */
    int holder = 0;
    for (; start_index < end_index; ++start_index, ++holder) {
        // holder가 짝수일 때는 I여야만 하고, 홀수일 때는 O여야만 함.
        if ((holder % 2 == 0 && S[start_index] != 'I') || (holder % 2 == 1 && S[start_index] != 'O')) {
            problem_index = start_index;
            return false;
        }
    }

    // 통과
    prev_complete_index = end_index;
    return true;
}

int main() {
    ios_base::sync_with_stdio(false); // 입출력 최적화
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> N >> M >> S;

    int i = 0;
    int cnt = 0;
    pattern_len = N * 2 + 1;
    while (i <= M - pattern_len) {
        if (S[i] == 'I') {
            if (check(i)) {
                ++cnt;
                ++i; // 만약 VALID 했다면, 다음 문자열은 무조건 'O' 이기 때문에 한번 스킵한다.
            } else {
                // 만약 중간에 틀렸다면, 문제 인덱스 이전까지 유효한 문자가 있을 수 없으므로 스킵
                if (i < problem_index) {
                    i = problem_index;
                    continue;
                }
            }
        }
        ++i;
    }

    cout << cnt;
    return 0;
}

---

끝.