19941(햄버거 분배)

첫 시도

• 시간제한이 0.5초 -> 5 * 10^7
• N이 2 * 10^4, K는 10이지만 왼쪽으로 10칸 또는 오른쪽으로 10칸이므로 20
• O(N(2K)) -> 4 * 10^5 이므로 완전탐색으로 충분히 해결 가능
• 백트래킹으로 구현 시도

해결

• 굳이 백트래킹으로 구현 하지 않아도 그리디하게 가장 왼쪽의 햄버거를 먹는 것으로 구현한다면 해결 가능
• 만약 왼쪽의 것을 먹을 수 있음에도 오른쪽을 먹는다면 이후에 다른 사람들이 못먹을 가능성이 있음 -> 먹을 수 있는 가장 왼쪽 햄버거부터 먹는 것이 최적해

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static int N,K, max;
    static boolean[] check;
    static String[] input;
    public static void main(String[] ars) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        max = 0;

        input = br.readLine().split("");
        check = new boolean[input.length];

        int result = 0;
        for(int i =0; i<N; i++){
            if(input[i].equals("P")) {
                result +=back(i);
            }
        }
        System.out.println(result);


    }

    static int back(int depth){
        for(int i = depth-K; i<=depth+K; i++){
            if(i<0 || i>=N) continue;
            if(!check[i] && input[i].equals("H")) {
                check[i] = true;
                return 1;
            }
        }
        return 0;
    }

}

참고

• 직접구현