[19941] 햄버거 분배

🔗 문제 링크

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

🔍 문제 설명

기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다.

햄버거	사람	햄버거	사람	햄버거	사람	햄버거	햄버거	사람	사람	햄버거	사람
1	2	3	4	5	6	7	8	9	10	11	12

위의 상태에서 $K = 1$인 경우를 생각해보자. 이 경우 모든 사람은 자신과 인접한 햄버거만 먹을 수 있다. 10번의 위치에 있는 사람은 11번 위치에 있는 햄버거를 먹을 수 있다. 이 경우 다음과 같이 최대 5명의 사람이 햄버거를 먹을 수 있다.

2번 위치에 있는 사람: 1번 위치에 있는 햄버거
4번 위치에 있는 사람: 5번 위치에 있는 햄버거
6번 위치에 있는 사람: 7번 위치에 있는 햄버거
9번 위치에 있는 사람: 8번 위치에 있는 햄버거
10번 위치에 있는 사람: 11번 위치에 있는 햄버거
12번 위치에 있는 사람: 먹을 수 있는 햄버거가 없음

$K = 2$인 경우에는 6명 모두가 햄버거를 먹을 수 있다.

2번 위치에 있는 사람: 1번 위치에 있는 햄버거
4번 위치에 있는 사람: 3번 위치에 있는 햄버거
6번 위치에 있는 사람: 5번 위치에 있는 햄버거
9번 위치에 있는 사람: 7번 위치에 있는 햄버거
10번 위치에 있는 사람: 8번 위치에 있는 햄버거
12번 위치에 있는 사람: 11번 위치에 있는 햄버거

식탁의 길이 $N$, 햄버거를 선택할 수 있는 거리 $K$, 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.

⚠️ 제한사항

• 1 ≤ N ≤ 20,000

• 1 ≤ K ≤ 10

---

🗝 풀이 (언어 : Java)

모든 케이스를 탐색해도 20만 번의 반복이므로, 전체 탐색이 가능하다. 본인 기준으로 가장 인접한 햄버거부터 먹어치우는 방식으로 구현했다.

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

public class Main {

    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());
        String[] hamburgerPerson = br.readLine().split("");
        br.close();
        solution(hamburgerPerson, k);
    }

    private static void solution(String[] hamburgerPerson, int k) {
        boolean[] visited = new boolean[hamburgerPerson.length];
        int answer = 0;
        hpLoop:
        for (int i = 0; i < hamburgerPerson.length; i++) {
            if (hamburgerPerson[i].equals("P")) {
                //좌
                for (int j = i - k; j < i; j++) { //가장 인접한 햄버거부터 먹기
                    if (j >= 0 && hamburgerPerson[j].equals("H") && !visited[j]) {
                        visited[j] = true; //이미 먹은 햄버거 표시
                        answer++;
                        continue hpLoop; //케이스 찾은 경우, 우측 탐색 생략
                    }
                }
                //우
                for (int j = i + 1; j <= i + k; j++) {
                    if (j < hamburgerPerson.length && hamburgerPerson[j].equals("H") && !visited[j]) {
                        visited[j] = true;
                        answer++;
                        break;
                    }
                }
            }
        }
        System.out.println(answer);
    }

}