백준 19941 - 햄버거 분배 (자바 - 그리디)

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

19941번: 햄버거 분배

 

* 문제 요약

기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여있다.

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

위의 상태에서 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, 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.

 

* 입력

첫 줄에 두 정수 N 과 K 가 있다. 그리고 다음 줄에 사람과 햄버거의 위치가 문자 P (사람) 와 H (햄버거) 로 이루어지는 길이 N 인 문자열로 주어진다.

 

* 출력

첫 줄에 햄버거를 먹을 수 있는 최대 사람 수를 나타낸다.

 

* 제한

- 1 <= N <= 20,000

- 1 <= K <= 10

 

* 예시

 

* 해결 과정

문자열을 왼쪽부터 탐색하면서 햄버거를 탐색한 경우엔 아무 로직도 수행하지 않은 체 다음 탐색으로 넘어가고, 사람을 탐색한 경우 아래와 같은 로직을 수행한다.

- 현재 인덱스를 기준으로 K 만큼 떨어진 거리 안에 햄버거가 있는지 탐색한다.

- 우선 현재 인덱스의 왼쪽으로 K 만큼 떨어진 거리 안에 햄버거가 있는지 탐색한다.

- 거리 안에 햄버거가 있는 경우 오른쪽 방향에 있는지 없는지와 상관없이 해당 햄버거를 먹은 것으로 상태를 변화시킨 후 정답 변수 result 의 값을 1 증가시키고 다음 인덱스 탐색으로 넘어간다.

- 먄약 왼쪽 방향으로 K 만큼 떨어진 거리 안에 먹을 수 있는 햄버거가 존재하지 않는 경우 오른쪽 방향을 살펴서 먹을 수 있는 햄버거가 있는 경우 해당 햄버거를 먹은 것으로 상태를 변화시킨 후 정답 변수 result 의 값을 1 증가시키고 다음 인덱스 탐색으로 넘어간다.

 

최종적으로 모든 문자열의 탐색이 끝나고 나면 반복문을 종료하고 정답 변수 result 값을 출력시킨다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        int count = Integer.parseInt(input[0]);
        int k = Integer.parseInt(input[1]);

        char[] table = new char[count];
        String str = br.readLine();
        for (int i = 0; i < str.length(); i++) {
            table[i] = str.charAt(i);
        }

        int result = 0;
        for (int i = 0; i < table.length; i++) {
            if (table[i] == 'H')
                continue;
            else if (table[i] == 'P') {
                boolean check = false;
                for (int index = i - k; index < i; index++) {
                    if (index < 0)
                        continue;
                    else {
                        if (table[index] == 'H') {
                            table[index] = 'E';
                            result++;
                            check = true;
                            break;
                        }
                    }
                }
                if (!check) {
                    for (int index = i; index <= i + k; index++) {
                        if (index > table.length - 1)
                            break;
                        else {
                            if (table[index] == 'H') {
                                table[index] = 'E';
                                result++;
                                break;
                            }
                        }
                    }
                }
            }
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

현재 상태에서 최적의 해답 -> 주어진 거리 안에서 가장 먼저 발견된 햄버거를 먹음

선택된 해가 문제의 조건을 만족하는지 검사 -> 주어진 거리 안에서 가장 먼저 발견된 햄버거를 먹을 경우 범위 안에서 현재 탐색중인 사람과 가장 멀리 있는 햄버거를 먹게되므로, 이후의 탐색으로 발견한 사람을 기준으로 다시 탐색을 했을 때 그 사람을 기준으로 한 범위 안에서 먹을 수 있는 햄버거가 존재할 확률이 더 올라간다.

결과적으로 햄버거를 먹을 수 있는 사람 숫자의 최대값에 가까운 값을 구할 수 있게 된다.

 

주어진 거리 안에서 가장 먼저 발견된 햄버거를 먹는 방식으로 뒤에 일어날 일 과는 독립적으로 현재 상태에서 최적의 해답을 찾았으며, 그 해답이 햄버거를 먹을 수 있는 사람의 최대 숫자를 구해야 하는 조건을 반드시 최적해라고 보장할 수 없으나, 그에 최대한 가까운 근사값으로 찾을 수 있으므로 그리디 알고리즘 문제에 해당된다.