[Java] 백준 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인 문자열로 주어진다.

출력

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

제한

•  1≤N≤20,000
•  1≤K≤10

예제 입력 1

20 1
HHPHPPHHPPHPPPHPHPHP

예제 출력 1

8

예제 입력 2

20 2
HHHHHPPPPPHPHPHPHHHP

예제 출력 2 

7

 

소스코드

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

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;
	
	private static int N, K, result=0;
	private static String s;
	private static boolean []visited;
	
	public static void main(String[] args) throws IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		st=new StringTokenizer(br.readLine());
		N=Integer.parseInt(st.nextToken());
		K=Integer.parseInt(st.nextToken());
		s=br.readLine();
	
		visited=new boolean[N];
		for(int i=0;i<s.length();i++) {
			if(s.charAt(i)=='P') {	// 사람 위치를 찾음
				for(int j=i-K;j<=i+K;j++) {	// 거리가 K 이하인 햄버거를 탐색함
					if(j>=N) break;	// 범위를 벗어나면 다음으로 넘어감
					if(j<0 || i==j || visited[j]) continue;	// 범위를 벗어나거나 이미 방문한 햄버거는 넘어감
					if(s.charAt(j)=='H') {	// 조건을 충족하는 햄버거를 찾으면 먹을 수 있는 것으로 판단
						visited[j]=true;
						result++;
						break;
					}
				}
			}
		}
		
		System.out.println(result);
	}

}

주어진 문자열의 각 사람마다 거리가 K 이하인 경우를 탐색하며 먹을 수 있는 햄버거를 탐색합니다. 이때 먹을 수 있는 햄버거를 찾은 경우, 해당 햄버거를 방문 처리 하고 다음 사람을 탐색합니다. 모든 사람을 탐색한 후 결과를 출력합니다.