[백준] 19941: 햄버거 분배 - JAVA

16 Sep 2023 in Algorithm on 그리디 알고리즘

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

풀이

사람과 햄버거가 한칸씩 차지하고 나열되어있다.

사람들은 자신의 위치에서 거리가 K이하인 햄버거를 하나 먹는다.

사람을 앞에서부터 보면서 거리가 K이하인 것중에 위치가 가장 앞인거을 먹게한다.

앞사람에게 앞햄버거를 배정하는 것이 최선의 경우이다.

---

메모리: 14388KB

시간: 136ms

언어: Java 11

코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        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());

        char[] arr = br.readLine().toCharArray();
        boolean[] visit = new boolean[N];

        int ans = 0;
        for (int i = 0; i < N; i++) {
            if (arr[i] == 'P') {
                for (int j = Math.max(0, i - K); j < Math.min(i + K + 1, N); j++) {
                    if (arr[j] == 'H' && !visit[j]) {
                        visit[j] = true;
                        ans++;
                        break;
                    }
                }
            }
        }

        System.out.println(ans);
    }

}