[백준] 5525번 - IOIOI

 

기존에 아래와 같이 문자열을 더해주는 형식으로 문제를 풀이하였는데 이는 서브테스크에서 50점이라는 점수만 받을 수 있는 코드였다.

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

public class p5525 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int a = Integer.parseInt(br.readLine());
		int b = Integer.parseInt(br.readLine());

		String s = "I";
		int index = a * 2 + 1;
		for (int i = 0; i < a; i++) {
			s += "OI";
		}
		int cnt = 0;
		String str = br.readLine();
		for (int i = 0; i < str.length() - index; i++) {
			if (str.substring(i, i + index).equals(s)) {
				cnt++;
			}
		}

		System.out.println(cnt);
	}
} 

 

따라서 코드를 아래와 같이 동적인 방식으로 변경하고 제대로된 해법으로 문제를 풀이할 수 있었다.

 

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

public class p5525 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int a = Integer.parseInt(br.readLine());
		int b = Integer.parseInt(br.readLine());

		String str = br.readLine();
		int answer = 0;
		int[] dp = new int[b];

		for (int i = 0; i < b; i++) {
			dp[i] = 0;
		}

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