문제 이해

햄버거와 사람이 단위 간격으로 놓여 있다.
이 때 사람들은 자신의 위치에서 K 이하로 거리가 떨어져 있는 햄버거만 먹을 수 있다.
(즉, index 차이가 K 이하로 나야 함)

이런 조건에서 햄버거를 먹을 수 있는 사람이 최대가 되는 사람 수를 구하는 문제이다.

문제 풀이

처음에는 DP 문제로 해결하려 했으나, 도저히 방법이 생각나지 않았다.
따라서, 그냥 범위 내 모든 영역을 확인해보는 방법으로 문제를 해결했다.

여기서 핵심적인 아이디어가 있었다.
어차피 K는 모든 사람에 있어 공통적으로 적용되어야 하는 값이다.
따라서, 만약 J번째 사람이 J-K ~ J+K번째 햄버거를 먹지 못한다면 (J+1)번째 사람은 J-K ~ J+K번째에 존재하는 모든 것을 섭취할 수 없다
(이전 사람이 섭취를 못했고, 다음 사람은 이전 사람보다 먹을 수 있는 햄버거 범위가 오른쪽으로 이동하기 때문에, 이전에 확인했던 부분은 못먹는 것이다)

이를 활용하여 문제를 해결했다.

코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {
		FastReader sc = new FastReader();

		int N = sc.nextInt(); // H & P 수
		int K = sc.nextInt(); // K
		String str = sc.next();
		
		int prev_eat = 0; 
        # 이전에 먹었던 햄버거 Index + 1
        # 즉, Search를 시작할 Index
        
		int num = 0;
		for(int i =0;i<N;i++) {
			if(str.charAt(i)=='P') { // Person일 경우에만 확인
				boolean check = false;
                
				int left = Math.max(prev_eat, i - K);
				int right = Math.min(i+K, N-1);
                // left ~ right 범위를 확인
                // i - K나 i + K개 Index 범위를 넘어설 수 있으므로 처리해 줬다
                
				for(int j = left;j<=right;j++) {
					if(str.charAt(j)=='H') {
                        /*
                        햄버거를 먹을 수 있는 상태
                        j번째 햄버거를 먹었으므로, 다음 사람은 j+1번째 index
                        부터 확인해보면 된다.
                        */
						prev_eat = j+1;
						num++;
						check = true;
						break;
					}
				}
				if(!check) {
                    /*
                    먹을 수 있는 햄버거가 left ~ right 범위에는 없음
                    따라서, 이 다음에 있는 Person들도 left ~ right에 존재하는
                    모든 햄버거를 먹을 수 없다.
                    
                    prev_eat은 Search를 시작하는 위치이다.
                    left ~ right은 확인할 필요가 없으므로 right+1로 값 지정
                    */
					prev_eat = right+1;
				}
				
			}
			
		}
		System.out.println(num);	
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
    }
}

결과

• 두번째 줄 틀렸습니다 : 먹을 수 있는 햄버거가 left ~ right 범위에는 없을 때, 이 다음 Search 해야하는 시작 위치는 right + 1이다. 하지만 생각을 잘못하여 (i+1)로 착각해 틀렸다.