[백준_1911] 흙길 보수하기 ( Greedy - 자바스크립트 )

문제

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

1911번: 흙길 보수하기

How to Solve ?

 

[1] 단순 구현

 

예시를 자세히 살펴보면, [1,6] [8,12] [13,17] 일 때 "3"인 널빤지가 총 5장이 필요하다.

왜 그럴까 생각해보면 < 1-6 > 웅덩이를 처리하는데 2장, <8-17> 웅덩이를 처리하는데 3장이 소요가 되는 것이다.

그리하여, 미리 웅덩이의 좌표를 확인하여 "다음 웅덩이의 시작 - 전 웅덩이의 끝 === 1" 이면 이전 웅덩이의 끝 값을 다음 웅덩이의 끝 값으로 설정 해주는 작업을 하였다.

function solve() {
  let answer = 0;

  // 웅덩이를 시작 지점을 바탕으로 정렬
  pools.sort(function (a, b) {
    if (a[0] === b[0]) {
      return a[1] - b[1];
    }

    return a[0] - b[0];
  });

  // 웅덩이 차이를 통해 좌표 정렬
  for (let i = N - 1; i > 0; i--) {
    let start = pools[i][0];
    let end = pools[i - 1][1];

    if (start - end === 1) {
      pools[i - 1][1] = pools[i][1];
      pools.splice(i, 1);
    }
  }

  for (let i = 0; i < pools.length; i++) {
    answer += Math.ceil((pools[i][1] - pools[i][0]) / L);
  }

  return answer;
}

const [N, L] = [2, 4];

const pools = [
  [1, 6],
  [13, 17],
  [8, 12],
];

 

[2] 그리디

 

그런데, 문제의 유형을 살펴보면 이 문제는 "그리디" 즉, 현재 위치에서 최선의 결과 값을 만드는 것을 권고하는 문제인데 "과연 좌표를 미리 정리 해놓으면 그리디 답게 문제를 푼걸까?" 라는 의문이 들었다.

 

뭐 사실 정답만 맞으면 굳이 그리디로 접근 할 필요는 없지만, 그리디가 가지는 속성을 조금 학습하고자! 방법을 고민 해보았다.

 

그렇다면, 현재의 위치에서 어떻게 최선의 선택을 내릴 수 있을까? 아까의 예시를 통해 한번 이야기 해보자

 

[1-6] 웅덩이에 널빤지를 2개 깔게 되면, 6까지 깔리게 된다. 즉, 넘치지 않게 사용 했기에 다른 널빤지가 더 붙더라도 <1-6> 섹터에서는 최적의 널빤지를 통해 웅덩이를 처리한 것이다.

 

하지만, [8-12] 의 경우 웅덩이의 길이가 널빤지의 길이인 "3"을 넘어서 2개를 사용 해야한다. 이 경우에는 널빤지를 깔게 되면 "14" 지점까지 깔리게 되는데 다음 웅덩이가 "14"보다 작은 13에서부터 시작을 한다.

 

즉, 이전의 널빤지를 통해 웅덩이의 일부가 막혀서 새로운 시작점이 설정이 된 것이다. 고로 [14-17]이 될 것이고, 이 지점에서 필요한 널빤지는 1장이다.

 

function solve() {
  let count = 0;
  let last = 0;

  for (let i = 0; i < pools.length; i++) {
    const [start, end] = pools[i];

    if (last >= end) continue; // 널빤지가 웅덩이를 모두 덮으면
    if (last > start) start = last; // 시작점 이상을 널빤지가 덮고 있으면

    last = start; // 이전의 널빤지가 시작점에 닿지 않음
    let need = Math.ceil((end - start) / L);
    count += need;
    last += need * L; // 널빤지가 닿는 곳을 재설정
  }

  console.log(count);
}

const [N, L] = [2, 4];

const pools = [
  [1, 6],
  [13, 17],
  [8, 12],
];

console.log(solve());

[3] 느낀점

결국에 다 짜보고 보니까, TopDown 과 BottomUp의 차이가 아니였을까 생각해본다. 미리 좌표를 건드렸다고 하더라도, 이전에 알고리즘을 보면 항상 시작점 -> 끝점으로 이동하는 루프만을 고려 했는데 알고리즘을 많이 풀다보니까 어느정도 사고가 유연해진 것 같기도 하다.