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

 

[입력]

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

 

[코드]

import java.util.*;

public class BaekJoon_19941 {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		int n=sc.nextInt(); // 사람 수
		int k=sc.nextInt(); // 햄버거를 선택할 수 있는 거리
		
		char[] table=new char[n]; // 테이블 상태
		boolean[] eat=new boolean[n]; // 먹은 햄버거인지 체크하는 함수
		
		String str=sc.next();
		for(int i=0;i<str.length();i++)
			table[i]=str.charAt(i);
		
		// 최대한 왼쪽의 멀리 있는 햄버거를 먹어야 최댓값이 나옴 -> 그 다음 우선순위 오른쪽
		for(int i=0;i<n;i++) {
			if(table[i]=='P') {
				int start=Math.max(i-k,0);
				int end=Math.min(i+k,n-1);
				
				// 왼쪽부터 탐색
				for(int j=start;j<=end;j++) {
					if(table[j]=='H'&&!eat[j]) {
						eat[j]=true; 
						break; // 햄버거 먹었으면 더이상 탐색 X
					}
				}
			}
			
		}
		
		// 먹은 햄버거 수 출력
		int count=0;
		for(int i=0;i<n;i++)
			if(table[i]=='H'&&eat[i])
				count++;
		
		System.out.println(count);
	}

}

 

[고찰]

 이번 문제는 최대한 멀리 있는 햄버거를 먹어야 최댓값이 나오는 문제였다. 따라서 사람의 위치에서 -K ~ +K 까지의 햄버거 중 먹을 수 있는 햄버거가 나온다면 boolean 배열 값을 바꾸고 탐색을 종료하는 방식으로 구현하면 정답 처리를 받을 수 있었다.