[Node.js] 백준 19941 - 햄버거 분배

함부기 함부기 함부기 함부기 여봐라~

…

햄버거를 최대한 많이 먹는 경우를 찾는 문제.

접근

식탁 위에 사람(P)과 햄버거(H)가 일렬로 놓여 있다. 각 사람은 자신의 위치로부터 K 거리 이내에 있는 햄버거를 단 하나만 먹을 수 있다. 최대한 많은 사람이 햄버거를 먹도록 하는 것이 목표.

=> 전형적인 그리디(Greedy) 알고리즘 문제의 형태. 각 단계에서 최선의 선택을 하여 전체 최적해를 도출하자.

인데!

~~가까이 있는걸 먹는게 정답은 아니라는.. 나중에 이 고민 나옴~~

첫 시도

사람을 앞에서부터 처리
자기 범위 내 가장 가까운 햄버거를 먹는다 = 햄버거가 많이 남으니 남들도 많이 먹을 수 있을 것.

코드

// ... (입력 처리 생략) ...

for (let i = 0; i < N; i++) {
  // 각 사람(P)을 왼쪽에서 오른쪽으로 처리
  if (table[i] === "P") {
    let isEaten = false;

    // 1. 왼쪽 K 범위 내에서 가장 가까운 햄버거부터 탐색 (j = 1 부터 K 까지 증가)
    for (let j = 1; j <= K; j++) {
      const leftIdx = i - j;
      if (leftIdx < 0) continue;
      if (table[leftIdx] === "H" && taken[leftIdx] === false) {
        taken[leftIdx] = true;
        ans++;
        isEaten = true;
        break;
      }
    }

    // 2. 왼쪽에서 못 찾으면, 오른쪽 K 범위 내에서 가장 가까운 햄버거부터 탐색 (j = 1 부터 K 까지 증가)
    if (!isEaten) {
      for (let j = 1; j <= K; j++) {
        const rightIdx = i + j;
        if (rightIdx >= N) continue;
        if (table[rightIdx] === "H" && taken[rightIdx] === false) {
          taken[rightIdx] = true;
          ans++;
          break;
        }
      }
    }
  }
}
// ... (출력 생략) ...

처음에는 입력 문제나, 사소한 인덱스 오류일 것이라 생각하고 3회정도 더 제출했으나 결국 실패.

새로운 가설과 정답

가장 멀리 있는 (왼쪽부터 보니까 왼쪽은 가장 멀리 있는 것)
오른쪽은 가장 가까운 것 (다음 사람에게는 왼쪽 햄버거가 되므로)

생각한 이유

왼쪽에서 가장 멀리 있는 햄버거를 먼저 집는다면, 내가 아니면 아무도 먹지 못할 햄버거이므로, “많이” 라는 조건에 맞다고 생각함
만약 왼쪽에 햄버거가 없다면, 오른쪽에서 가장 가까운 햄버거를 집는다. == 가장 효율적인 선택.”

코드

const fs = require("fs");
const input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim() // '\r' 제거를 잊지 않았습니다!
  .split("\n");

const [N, K] = input[0].split(" ").map(Number);

const table = input.slice(1)[0].split("");
const taken = Array(N).fill(false); // 햄버거 집힘 여부 배열, 올바르게 초기화

let ans = 0; // 햄버거를 먹은 사람 수

for (let i = 0; i < N; i++) {
  // 각 사람(P)을 왼쪽에서 오른쪽으로 처리
  if (table[i] === "P") {
    let isEaten = false; // 현재 사람이 햄버거를 먹었는지 여부

    // 1. 왼쪽 K 범위 내에서 가장 먼 햄버거부터 탐색
    // j를 K부터 1까지 감소시키면서 현재 위치(i)에서 왼쪽으로 j칸 떨어진 곳을 확인
    for (let j = K; j >= 1; j--) {
      // K부터 1까지 감소!
      const leftIdx = i - j; // 왼쪽 햄버거의 인덱스
      if (leftIdx < 0) continue; // 범위 밖이면 건너뜀

      // 햄버거('H')이고 아직 집히지 않았다면
      if (table[leftIdx] === "H" && taken[leftIdx] === false) {
        taken[leftIdx] = true; // 햄버거를 집음
        ans++; // 카운트 증가
        isEaten = true; // 먹었음을 표시
        break; // 햄버거를 찾았으니 더 이상 탐색할 필요 없음
      }
    }

    // 2. 왼쪽에서 햄버거를 찾지 못했다면, 오른쪽 K 범위 내에서 가장 가까운 햄버거부터 탐색
    // j를 1부터 K까지 증가시키면서 현재 위치(i)에서 오른쪽으로 j칸 떨어진 곳을 확인
    if (!isEaten) {
      for (let j = 1; j <= K; j++) {
        // 1부터 K까지 증가!
        const rightIdx = i + j; // 오른쪽 햄버거의 인덱스
        if (rightIdx >= N) continue; // 범위 밖이면 건너뜀

        // 햄버거('H')이고 아직 집히지 않았다면
        if (table[rightIdx] === "H" && taken[rightIdx] === false) {
          taken[rightIdx] = true; // 햄버거를 집음
          ans++; // 카운트 증가
          break; // 햄버거를 찾았으니 더 이상 탐색할 필요 없음
        }
      }
    }
  }
}
console.log(ans);

결론과 교훈

그리디는 항상 가까운 것이 정답이 아니다. -> 나 아니면 못 먹을 가능성이 높은 자원을 확보하는 것이 정답일 수 있다.
“햄버거를 생존시키자” : 뒤늦게 발견되어 버려질 수 있는 멀리있는 햄버거를 선제적으로 선택하여, 살려간다. => 타인에게 영향을 덜 미치며, 동시에 햄버거 소비량을 증가시킴
이런저런 가설로 “틀렸습니다” 를 두려워 하지 말자.

햄버거… 햄버거 그만.