[백준 19941번] 햄버거 분배

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

 

package greedy;

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

public class Greedy19941 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int cnt = 0;
        String line = br.readLine();
        char[] arr = line.toCharArray();

        for (int i = 0; i < N; i++) {
            if (arr[i] == 'P') {
                int startIndex = Math.max(i - K, 0);
                int endIndex = Math.min(i + K, N-1);

                for (int j = startIndex; j <= endIndex; j++) {
                    if (arr[j] == 'H') {
                        cnt++;
                        arr[j] = 'X';
                        break;
                    }
                }

            }
        }

        System.out.println(cnt);

    }
}

 

문제는 엄청 간단했다. 그냥 이중 for문돌려서 하면 되는건데 뭔가 시간초과가 뜰거 같애서 계속 효율적으로 설계하다가 망해버려서 맨 처음 코드로 냈더니 성공..... 내 시간 돌려내!!!

 

이 문제의 핵심은 startIndex와 endIndex 이다. 이를 잘 이용해서 P가 뒤 또는 앞으로 햄버거를 먹을 수 있게 해야된다.