[BOJ] 19941 햄버거 분배 (Java)

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

 

처음으로 그리디 문제 읽으면서 떠오른 생각

왼쪽에 있는 버거부터 먹어야 사람이 먹을 수 있는 버거의 수가 최대가 된다.

사람을 만났을 때 왼쪽부터 k만큼 탐색해서 버거가 있으면 먹고, 없으면 오른쪽 버거를 먹으면 된다.

한번 먹은 버거는 또 먹을 수 없으니 check 배열로 먹은 버거는 체크해준다.

 

 

<제출 코드>

package BOJ.Greedy;

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

public class BOJ_19941_햄버거분배 {

    static int n, k;
    static int ans;
    static char[] arr;

    public static void eatBuger(){
        boolean[] check = new boolean[n];
        // 사람 위치에서 왼쪽에 있는 버거부터 먹고, 없으면 오른쪽 버거 먹음.
        for(int i=0; i<n; i++){
            if(arr[i] == 'P'){
                for(int j=i-k; j<=i+k; j++){
                    // 범위 벗어나면 제외
                    if(j < 0 || j >= n) continue;
                    // 버거가 있으면 먹고 먹은 표시하고 끝
                    if(arr[j] == 'H' && !check[j]){
                        ans++;
                        check[j] = true;
                        break;
                    }
                }
            }
        }
    }

    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 char[n];
        arr = br.readLine().toCharArray();

        eatBuger();
        System.out.println(ans);
    }
}