baekjoon/Greedy
백준 19941번 : 햄버거 분배 [자바]
Meluu_
2025. 3. 13. 10:56

🧫 문제 분석
✔️ 출처
📖 문제

앞의 사람이 가장 왼쪽 즉, 거리가 먼 것 부터 먹어줘야 뒤에 사람이 선택지가 늘어난다.
따라서 앞의 사람이 현재 위치-k ~ 현재 위치 + k 까지 탐색해서 앞쪽에 있는 아직 안먹은 햄버거가 있다면 먹는다.
쉬운 문제인데 이런 유형을 까먹을까봐 기록함으로써 이해한다.
🔅 문제 풀이
import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
boolean[] eatCheck = new boolean[n];
char[] tables = br.readLine().toCharArray();
ArrayList<Integer> people = new ArrayList<>();
// 사람의 인덱스를 저장
for (int i = 0; i < n; i++) {
if (tables[i] == 'P') {
people.add(i);
}
}
int cnt = 0;
for (int idx : people) {
for (int i = idx - k; i <= idx + k; i++) {
if (i < 0 || i >= n) continue;
// 햄버거이고 아직 안먹었다면 먹음 처리
if (tables[i] == 'H' && !eatCheck[i]) {
eatCheck[i] = true;
cnt++;
break;
}
}
}
bw.write(cnt+ "");
bw.flush();
bw.close();
}
}