백준_5525 IOIOI(자바) / 문자열

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.Back;

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

public class Back_5525 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		char[] s = br.readLine().toCharArray();
		int[] dp = new int[M];
		int ans=0;
		
		for (int i = 1; i < M-1; i++) {
			if(s[i]=='O'&&s[i+1]=='I') {
				dp[i+1] = dp[i-1]+1;
				
				if(dp[i+1]>=N&& s[i - 2 * N + 1] == 'I')
                    ans++;
			}
		}
		System.out.println(ans);
	}
}

 

- 문자열에 DP를 적용시켜서 해결을 해봤습니다.

 

- 문제 풀이에 어려움이 있어서 다른 사이트를 참고해서 해결을 했습니다....

 

- DP의 방법을 이해하니까 정말 쉽게 풀리는 문제였습니다.

 

- OI 부분이 반복 되기 때문에 문제에서 요구되는 만큼의 OI 갯수를 파악하는 것을 DP를 이용해서 해결을 했습니다.

 

- 요구하는 갯수 이상이 되면, 요구되는 부분 앞에 I가 있는지 확인을 해줍니다.

 

 

- 여기 사이트를 참고해서 풀었습니다

 https://girawhale.tistory.com/11