누적합 - 개똥벌레

예전에 프로그래머스에서 비슷한, 아마 총을 어디서 쏴야 한번에 제일 많은 장애물이 맞는지 찾는 그런 문제였었는데 그때는 어떻게 접근해야할지 몰라서 못풀었었는데, 강의를 들으면서 완전탐색과 누적합을 배우고 나서 마주하니 생각보다 쉽게 접근이 가능했다.

일단 높이를 순회하면서 각각 장애물에 몇번 부딪히는지 찾아도 되지만, 완전 탐색적 사고인것 같아서 누적합 방식으로 접근했다.

장애물들을 순회하면서 각각의 높이에 부딪히는 횟수들을 누적하는 방식으로 풀이했다.

const Answer = (width, height, list) => {
  // 높이 object
  let heights = {};
  for (let i = 1; i <= height; i++) {
    heights[i] = 0;
  }

  list.forEach((stone, index) => {
    const num = index + 1;
    // 짝수일때, 종유석(위에서 아래로)
    // 높이도 위에서부터 1
    if (!(num % 2)) {
      // 짝수일 때 sotne보다 작거나 같은 높이들 +1
      for (let crashHeight = 1; crashHeight <= stone; crashHeight++) {
        heights[crashHeight] += 1;
      }
    } else {
      // stone보다 큰
      // height=5 종유석이 1일때 1 2 3 4 까지 안전
      //   아래에서 부터 올라가는
      for (let crashHeight = 0; crashHeight < stone; crashHeight++) {
        heights[height - crashHeight] += 1;
      }
    }
  });


  //   최솟값 도출
  const minValue = Math.min(
    ...Object.entries(heights).map(([height, breakNum]) => breakNum)
  );
  //   최솟값으로 부딪히는 경우의 수 도출
  console.log(
    minValue,
    Object.entries(heights).filter(
      ([height, breakNum]) => breakNum === minValue
    ).length
  );
};