백준 5525번 : IOIOI(Java)

https://www.acmicpc.net/problem/5525

5525번: IOIOI

 

---

[풀이]

 

 처음에는 해당하는 길이의 문자열을 substring으로 자른 후, for문을 돌면서 일치할 경우 answer++을 하는 식으로 풀었는데 그렇게 되니 50점밖에 얻지 못했다.(서브태스크) 그래서 DP를 이용해서 "IOI"가 일치할 경우 dp의 배열에 1씩 더하며 N의 개수 이상이 될 경우 answer++하는 방식으로 풀었다. 백준에서 문제를 풀면서 서브태스크가 있는 경우를 이전에는 풀어보지 못해서 처음에는 이게..뭐지..?? 왜 50점이지... 라고 생각했는데 효율성관련 문제였던 것 같다. 

 

 다른 사람들의 풀이를 보니, char 배열을 이용해서 푼 분도 있고, "OI"가 반복된다는 점을 이용해서 푼 분도 계신 것 같은데 그러한 부분도 읽어보고 익혀야 할 것 같다.

 

---

[코드]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bufferedReader.readLine());
        int M = Integer.parseInt(bufferedReader.readLine());
        String str = bufferedReader.readLine();
        int answer = 0;
        int[] dp = new int[M];

        Arrays.fill(dp, 0);

        for (int i = 2; i < M; i++) {
            String temp = str.substring(i - 2, i + 1);
            if (temp.equals("IOI")) {
                dp[i] = dp[i - 2] + 1;
            }
            if (dp[i] >= N) {
                answer++;
            }
        }
        System.out.println(answer);
    }
}