백준 19941: 햄버거 분배 - javascript (그리디)

문제 출처 

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

 

19941번: 햄버거 분배

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초 (추가 시간 없음)

256 MB

10871

5279

4294

50.093%

문제

기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 �$K$ 이하인 햄버거를 먹을 수 있다.

햄버거	사람	햄버거	사람	햄버거	사람	햄버거	햄버거	사람	사람	햄버거	사람
1	2	3	4	5	6	7	8	9	10	11	12

위의 상태에서 �=1$K = 1$인 경우를 생각해보자. 이 경우 모든 사람은 자신과 인접한 햄버거만 먹을 수 있다. 10번의 위치에 있는 사람은 11번 위치에 있는 햄버거를 먹을 수 있다. 이 경우 다음과 같이 최대 5명의 사람이 햄버거를 먹을 수 있다.

• 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
• 4번 위치에 있는 사람: 5번 위치에 있는 햄버거
• 6번 위치에 있는 사람: 7번 위치에 있는 햄버거
• 9번 위치에 있는 사람: 8번 위치에 있는 햄버거
• 10번 위치에 있는 사람: 11번 위치에 있는 햄버거
• 12번 위치에 있는 사람: 먹을 수 있는 햄버거가 없음

 �=2$K = 2$인 경우에는 6명 모두가 햄버거를 먹을 수 있다.

• 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
• 4번 위치에 있는 사람: 3번 위치에 있는 햄버거
• 6번 위치에 있는 사람: 5번 위치에 있는 햄버거
• 9번 위치에 있는 사람: 7번 위치에 있는 햄버거
• 10번 위치에 있는 사람: 8번 위치에 있는 햄버거
• 12번 위치에 있는 사람: 11번 위치에 있는 햄버거

식탁의 길이 �$N$, 햄버거를 선택할 수 있는 거리 �$K$, 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

제한

•  1≤�≤20,000$1 \le N \le 20,000$ 
•  1≤�≤10$1 \le K \le 10$ 

예제 입력 1 복사

20 1
HHPHPPHHPPHPPPHPHPHP

예제 출력 1 복사

8

예제 입력 2 복사

20 2
HHHHHPPPPPHPHPHPHHHP

예제 출력 2 복사

7

문제 풀이 힌트 

- 나한테서 가장 먼 햄버거를 먹을 때, 가장 많은 사람이 햄버거를 먹을 수 있다. 

- 가장 먼 것이 두개라면 그 중에서도 왼쪽에 있는 걸 먹어야 한다. (그래야 오른쪽에 있는 사람들한테 더 먼 햄버거를 해치워주는 것이다. 오른쪽에 있는걸 먹으면 그 사람 기준으로 오른쪽에 있는 사람들한테 가까운 햄버거를 먹는 나쁜 심보임) 

문제 풀이 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const [N, K] = input.shift().split(' ').map(v => +v); //식탁 길이, 햄버거 선택할 수 있는 거리 
const table = input[0].split(''); 

let answer = 0; 
for(let i=0; i<N; i++){
    if(table[i] === 'P'){ //사람일 때 
        let start = i-K;  //그 사람 위치 기준으로 왼쪽
        let end = i+K; //그 사람 위치 기준으로 오른쪽
        for(let j=start; j<=end; j++){ //start, 왼쪽부터 찾아본다. 
            if(table[j] === 'H'){ //만약 햄버거를 발견하면? 
                table[j] = 0; //먹은거 체크 
                answer++; //먹은 사람 수 +1
                break; //안의 반복문 끝낸다. 
               }     
            }
        }
    }
console.log(answer);

Only 문제 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const [N, K] = input.shift().split(' ').map(v => +v);
const table = input[0].split(''); 

let answer = 0; 
for(let i=0; i<N; i++){
    if(table[i] === 'P'){
        let start = i-K;  
        let end = i+K; 
        for(let j=start; j<=end; j++){
            if(table[j] === 'H'){
                table[j] = 0;
                answer++; 
                break; 
               }     
            }
        }
    }
console.log(answer);