백준 19941. 햄버거 분배

www.acmicpc.net/problem/19941

19941번: 햄버거 분배

문제제목 : 햄버거 분배

문제난이도 : 실버3

문제유형 : 그리디

 

문제

기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 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 <= 20000
• 1 <= K <= 10

아이디어

햄버거와 사람을 배열에 삽입한다. for문을 돌려 사람이 나오면, 접근할 수 있는 거리 중 가장 왼쪽에 있는 햄버거를 선택하는 것이 가장 최적의 선택이다.  

코드

package week5;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ19941 {
	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] input_num = br.readLine().split(" ");
		int N = Integer.parseInt(input_num[0]); // 라인
		int K = Integer.parseInt(input_num[1]); // 접근 가능 거리

		String[] line = br.readLine().split("");

		boolean[] visited = new boolean[N]; // 선택했는지의 유무
		int count = 0;

		for (int i = 0; i < N; i++) {
			if (line[i].equals("P")) { // 사람인 경우
				visited[i] = true;
				for (int j = K * -1; j <= K; j++) {
					if ((i + j) < 0 || (i + j) >= N) {
						continue;
					}
					if (line[(i + j)].equals("H") && !visited[(i + j)]) {
						// 방문안했고, 접근가능한 햄버거일 경우
						visited[(i + j)] = true;
						count++;
						break;
					}
				}
			}
		}
		System.out.println(count);
	}
}

 

후기

처음에 문제를 읽었을 때 이게 BFS문제인지 헷갈렸다. 사람이 인접한 위치의 햄버거를 선택할 수 있어서 BFS인가 생각했는데, 읽다보니까 어차피 일자로 되어있는 라인에서, 맨 왼쪽 사람부터 가장 왼쪽에 있는 부품을 선택하고 다음 사람도 자기의 가장 왼쪽에 있는 부품을 택하면 많은 사람들이 햄버거를 선택할 수 있겠구나 라고 생각해서 그리디알고리즘이라는 걸 확신했다. 오타와 조건식 사이에서 헤매다가 1분을 남기고 1개의 TC를 통과해서 그냥 제출해버렸는데, 이후에 확인해보니 for문 조건문이 잘못되었다 헤헤헤헤헤헤헤헤!!! 5분만 더 있었어도 고칠 수 있었을텐데...아쉽다! 그래도 실제 코테가 아니니까 우헤헤힣헤헿ㅎㅎ!!!!항상 이클립스로 문제풀다가 완전한 자동완성기능없이 푸려니까 많은 오타사이에서 헤맸다....ㅎ 타입도 알맞은 타입으로 바꿔줘야하는데 그것도 스킵해버리고... 아무튼 많은 실수를 경험할 수 있는 좋은 기회였다! 실전에서 실수만 안하면 되니까!! 연습할 때 실수를 많이하는 것은 좋은 것이다~!