[백준/JAVA] 19941번: 햄버거 분배

🔺 문제

19941번: 햄버거 분배

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        int N = Integer.parseInt(st.nextToken());   // 식탁 길이
        int K = Integer.parseInt(st.nextToken());   // 햄버거 선택 가능 거리
        
        char[] cmd = br.readLine().toCharArray();
        boolean[] isUsed = new boolean[cmd.length];
        
        int cnt = 0;
        
        // [x - K, x + K]
        for(int i = 0 ; i < N ; i++) {
            if(cmd[i] == 'P') {
                for(int j = i - K ; j <= i + K ; j++) {
                    if(0 <= j && j < N && cmd[j] == 'H' && !isUsed[j]) {
                        isUsed[j] = true;
                        cnt++;
                        break;
                    }
                }
            }
        }
 
        System.out.println(cnt);
    }
}

✅ 해결 아이디어
✔ 그리디
- 식탁의 현재 위치 i 에 사람이 있으면,
  인접한 [i - K, i + K] 구간에서 0이상 N 미만 범위를 벗어나지 않고,
  인접 위치에 있는 게 햄버거이고, 해당 햄버거를 먹을 수 있을 때
  햄버거를 먹을 수 있다고 판단한다.

 

💥 유의사항

• 인접한 부분의 범위가 0 이상 N 미만을 넘어가지 않는지 잘 따져주기 !

 

 

---

🔺 다른 풀이들

- 1. 구간 범위 설정 중, 0 범위를 벗어나는 값이면 0으로, N 이상인 값이면 N-1로 조정하는 과정이 포함되어 있다.

  2. 그리고 방문처리는 boolean 배열 사용하는 대신, 상관없는 다른 문자로 바꾸는 식으로 하셨다.

백준 19941번 : 햄버거 분배

 

---

💬 느낀 점

처음에 19랑 20번째 줄 순서 바껴서 틀렸었다.

잘 생각해보고 하자,,!

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 문제 풀이 참고

19941번 : 햄버거 분배