백준[19941] - 햄버거 분배

• 문제: https://www.acmicpc.net/problem/19941
• 분류: 그리디
• 난이도: S3
• 소요시간: 10m
• 자아성찰:
  • • 그리디 알고리즘의 특성을 잘 알 수 있는 문제라고 생각한다.
    • "가장 왼쪽에 있는 햄버거를 먹어야 다음 사람이 먹을 햄버거의 경우의 수가 늘어난다" 까지는 바로 떠올랐다.
    • 하지만 위 조건에만 너무 심취해서 "범위 내 왼쪽에 햄버거가 없다면, 오른쪽에서 가장 가까운 햄버거를 먹는다" 라는 조건을 놓쳐 처음 제출 했을 때 틀렸다.
      • HPHPHPHPHP 형태라면, 오른쪽에 햄버거를 먹어야 최대가 된다.
      • 이 때에는 왼쪽과 반대로 가장 가까운 햄버거를 먹어야 다음 사람(오른쪽 사람)이 먹을 수 있는 햄버거의 경우의 수가 늘어난다.

19941번: 햄버거 분배

---

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

public class B_19941 {

    static String s;
    static int[] arr;
    static int N, K, result = 0;
    static final int H = 0;
    static final int P = 1;
    static final int EAT = -1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        arr = new int[N];
        s = br.readLine();
        // 햄버거, 사람 구분지어 저장
        for (int i = 0; i < N; i++) {
            arr[i] = s.charAt(i) == 'H' ? H : P;
        }
        for (int i = 0; i < N; i++) {
            int target = arr[i];
            // 사람이 아니라면 넘어간다.
            if (target != P) continue;
            // 왼쪽 햄버거를 먹었는지 여부 판단
            boolean isEat = false;
            for (int j = i - K; j < i; j++) {
                // 범위 유효성 검사
                if (j < 0) continue;
                // 가장 먼 햄버거인 경우 먹음
                if (arr[j] == H) {
                    arr[j] = EAT;
                    result++;
                    isEat = true;
                    break;
                }
            }
            // 왼쪽에 햄버거가 없다면 오른쪽 탐색
            if (!isEat) {
                for (int j = i + 1; j <= i + K; j++) {
                    if (j >= N) break;
                    // 가장 가까운 햄버거인 경우 먹음
                    if (arr[j] == H) {
                        arr[j] = EAT;
                        result++;
                        break;
                    }
                }
            }
        }
        System.out.println(result);
    }
}