[BOJ] 19941번 "햄버거 분배" C언어 풀이

문제

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

20 1
HHPHPPHHPPHPPPHPHPHP

2.

20 2
HHHHHPPPPPHPHPHPHHHP

출력 예시

1.

8

2.

7

답안

코드

#include<stdio.h>
#define _CRT_SECURE_NO_WARNINGS


char jingburger[20001];


int main() {

	int count=0, input, k;

	scanf("%d %d", &input, &k);
	scanf("%s", jingburger);

	for (int i = 0; i < input; i++) {
		if (jingburger[i] == 'P') {
			for (int j = i - k; j <= i + k; j++) {
				if (0 <= j && j < input && jingburger[j] == 'H') {
					jingburger[j] = '0';
					count++;
					break;
				}
			}
		}
	}

	printf("%d", count);

	return 0;
}

 

풀이

우선 문제에 대해서 이해할 필요가 있을 것 같다.(처음에 이해 안되서 머리가 좀 아팠음)

 

 위 사진에서는 H와P로 이루어진 길이 12의 문자열이 있다. 위 배열에서 K=2라고 가정할 때 P가 접근할 수 있는 H는 아래와 같다.

 

 각 P의 위치에서 2칸 이내에 H에 접근하여 총 6명이 H를 먹을 수 있다고 칸다. 

 

n 값과 k 값을 input과 k 변수를 통해 입력 받고, H와 P로 이루어져 있는 문자열을 배열 jingburger에 저장한다. 그리고 for문을 통해 입력 받은 문자열을 하나하나 보면서  P가 있는지 찾아본다. 만일 P가 있으면 i-K와 i+k 만큼의 배열을 검사 한 다음에 H가 있다면 H를 0으로 바꾸고 count++을 하며 반복문을 break 한다. 이것을 반복하여 P가 접근할 수 있는 H가 없으면 count를 출력하여 몇 명이서 햄버거를 섭취할 수 있는지 나타낸다