[백준] 5525번: IOIOI - JAVA

🔗 문제 링크

BOJ 5525번: IOIOI

5525번: IOIOI

 

📝 풀이 과정

문제에서 핵심은 $P_N$에서 O는 N개만큼 들어있다는 점이다.
따라서, 현재 칸까지 'OI'가 몇 개 반복되었는지 누적하도록 하였다.

예를 들어, N = 1, S = OOIOIIOII인 경우를 살펴보자.

위와 같이 arr = M.toCharArray()이고, memo는 'OI'의 누적 갯수를 저장할 배열들이고, ans는 $P_N$이 몇 개 들어가는지 저장할 변수이다.

 

 

i = 1일 경우, arr[i + 1]의 값이 'I'이므로 memo[i + 1]의 값은 증가했지만 arr[i - 2 * N + 1]의 값이 'I'가 아니기 때문에 ans는 증가하지 않았다.

 

 

🤔 왜 arr[i - 2 * N + 1]일까?
N = 2이고, 현재 i = 3이라고 가정해보자.

[i + 1]에서 'OI'가 연속으로 2개 등장하였기 때문에 ans값을 증가시켜야할지 테스트를 해야할 시점이다.
하지만 arr[0]의 값이 'O'기 때문에 올바른 경우가 아닌데 이때 arr[i + 1]에서 arr[0]은 2 * N만큼 떨어져있기 때문에 arr[i + 1 - 2 * N]의 값을 확인하면 된다!

 

 

이어서, i의 값이 4가 되었을 때 memo[i - 1]값에 이어 연속으로 'OI'가 등장했으므로, memo[i + 1] = memo[i - 1] + 1값을 대입해준다.

 

이 때, arr[i - 2 * N + 1]의 값 또한 'I'므로 ans의 값을 증가시켜준다.

위와 같은 방식으로 진행한다면 memo의 값이 1을 넘으면서 앞의 값이 'I'를 만족하는 경우는 2가지가 나오게 된다.

 

💻 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), M = sc.nextInt();

        char[] arr = sc.next().toCharArray();
        int[] memo = new int[M];
        int ans = 0;

        for (int i = 1; i < M - 1; i++) {
            if (arr[i] == 'O' && arr[i + 1] == 'I') {
                memo[i + 1] = memo[i - 1] + 1;

                if (memo[i + 1] >= N && arr[i - 2 * N + 1] == 'I')
                    ans++;
            }
        }

        System.out.println(ans);

    }
}

 

📊 제출 결과