치춘짱베리굿나이스

[백준] 5525 본문

C C++/알고리즘풀이

[백준] 5525

치춘 2023. 9. 22. 20:44

IOIOI

문제

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

  • P1 IOI
  • P2 IOIOI
  • P3 IOIOIOI
  • PN IOIOI...OI (O가 N개)

IO로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

출력

S에 PN이 몇 군데 포함되어 있는지 출력한다.

풀이

#include <iostream>
#include <string>

int main(void) {
    int n, m, cnt = 0, nOfOIs;
    std::string str;

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    std::cin >> n >> m;
    std::cin >> str;

    for (int i = 0; i < m; i++) {
        nOfOIs = 0;
        if (str[i] == 'O')
            continue;
        while (str[i + 1] == 'O' && str[i + 2] == 'I') {
            nOfOIs++;
            i += 2;
            if (nOfOIs == n) {
                nOfOIs--;
                cnt++;
            }
        }
    }
    std::cout << cnt << "\n";
}

반성회

  1. I 를 찾으면 그 뒤에 따라오는 OI의 개수를 센다
    1. nOfOIsOI의 개수
    2. 인덱스 iOI마다 2씩 올라간다
  2. 만약 OI의 개수 nOfOIsn개를 달성할 경우
    1. cnt를 1 올린다 (원하는 IOIOI… 1개 발견)
    2. nOfOIs를 1 깎는다
      • IOIOIOI… 에서 첫 번째 IOIOI…를 찾았다면 앞의 IOIOI…에서 OI 개수를 1개 줄이는 이유는 그 다음 OI 부터 다음 IOIOI...를 찾기 시작하기 때문
      • 이 원리로 for 문을 한 번만 돌아서 IOIOI…를 찾을 수 있다

'C C++ > 알고리즘풀이' 카테고리의 다른 글

[백준] 19947  (0) 2023.09.26
[백준] 1916  (0) 2023.09.24
[백준] 12871  (0) 2023.09.21
[백준] 5648  (0) 2023.09.20
[백준] 3060  (0) 2023.09.18
Comments