[JS] 프로그래머스 금과 은 운반하기

https://school.programmers.co.kr/learn/courses/30/lessons/86053

프로그래머스

 

다시 풀어봐야 하는 문제이다.

먼저 시간복잡도 때문에 이분탐색이라는 것을 추론해냈다. (주석에 보면 소거법으로 구했다.)
그러고 나서 시간을 기준으로 풀어야 한다는 것도 파악했다.

근데 그 안에 제한 시간이 주어진다면 그 안에 무엇을 해야 할지 알 수 없었다.

(과정이 복잡했다. 금을 구해야 하는지 혹은 은만 구해야 하는지 혹은 둘 다 적절히 구해야 하는지 말이다.)

따라서 찾아보니 이런 경우에는 금만 구하는 경우, 은만 구하는 경우, 둘 다 적절히 구하는 경우 이 모든 경우를 구한 뒤에 합산해서 구할 수 있는지를 판단하는 것이었다. (코드에 나와 있다.)

 

수식으로 설명하자면

모든 경우 = 금만 채굴 | 금과 은 적절히 채굴 | 은만 채굴

-> 따라서 이 세 가지의 경우를 배열을 순환하면서 합산한 다음 구해야 하는 금, 은, 금 + 은 양보다 크거나 같은지를 파악하면 되었다.

 

음. 좀 더 쉽게 설명하자면 전체 확률을 표로 나타내면 아래와 같다.

	금 채굴하는 횟수	은 채굴하는 횟수
금만 채굴하는 경우	전체	0
금과 은 적절히 채굴	1 ~ (전체 - 1)	(전체 - 1) ~ 1
은만 채굴	0	전체

 

이 문제는 금과 은을 적절히 채굴하는 경우를 구하기가 너무 어려워서 그냥 저 세 가지의 경우를 모두 블랙박스로 구해야 했다.

 

이제 반복문 안의 하나의 경우만 보면 된다.

g[i], s[i], w[i], t[i]이고 제한 시간이 limit인 경우

금만 채굴하는 경우 금의 개수 gold, 은만 채굴하는 경우 은의 개수 silver, 금과 은 적절히 채굴하는 경우 both라고 하면

아래와 같이 풀면 된다.

 

1) 먼저 시간에 따른 최대 횟수를 구한다.

// 참고로 마지막 횟수가 아니라면 모두 왕복하므로 t[i]가 아닌 t[i] * 2로 나눈다.

let maxTimes = Math.floor(limit / (t[i] * 2));

// 마지막 횟수라면, 즉 제한 시간을 왕복 시간으로 나눈 나머지가 편도 시간보다 크다면 편도 횟수를 한 번 추가해준다.

if ((limit % (t[i] * 2) > t[i]) maxTimes++;

 

2) 횟수에 따른 최대 무게를 구한다.

const maxWeight = maxTimes * w[i];

 

3) 금만 채굴하는 경우, 은만 채굴하는 경우, 금과 은 적절히 채굴하는 경우에 넣어준다.

// 이 때 Math.min을 사용하는데 최대 채굴량이 실제로 채굴할 수 있는 양보다 크면 안되기 때문이다.

gold += Math.min(g[i], maxWeight);

silver += Math.min(s[i], maxWeight);

both += Math.min(g[i] + s[i], maxWeight);

 

드디어 마지막이다.

반복문을 빠져나와서 (배열을 모두 순회한 다음)

금, 은, 둘 다 채굴한 경우가 채굴해야 하는 양보다 크거나 같으면 성공이다.

gold >= a && silver >= b && both >= a + b 성공!

 

그래서 그 다음에 무엇을 하냐고?

이제 이분 탐색을 해야 한다.

 

우리는 방금 Down-Top 방식으로

임의의 제한 시간 limit을 주고 반복문을 순회하면서 제한 시간 안에 성립하는지 안하는지 구했다.

 

따라서 이제는 제한 시간을 어떻게 구하는지 이분 탐색으로 구해야 한다.

제약 조건을 통해서 처음 시간과 끝 시간을 구한다.

그러고 while문 안에서 mid = Math.floor((start + end)/2);가 제한 시간 limit가 되면서 돌아간다.

 

제한 시간 안에 통과하면 end = mid - 1로 줄여서 다시 시도해본다.

제한 시간 안에 통과하지 못한다면 start = mid + 1로 늘려서 다시 시도해본다.

start <= end로 될 때까지 한다.

 

위는 이분 탐색 알고리즘이다. (이해했다면 넘어가도 된다.)

여기에서 왜 start <= end일까?

- start < end이고 배열이 [?, true, ?, ?]라고 하면 start = 0, end = 3일 때 mid = 1일 때 true이므로(예시 배열 참고)

그 다음 end는 0이 된다. 그렇다면 start = 0, end = 0이 되면서 while문을 빠져나온다. 그렇다면 배열[1]이 true이므로 그 뒤의 모든 값은 true로 알 수 있지만 배열[0]의 값은 알 수 없다. 따라서 등호를 붙여야 한다.

- 쉽게 말하면 그냥 start = mid + 1이고 end = mid - 1이기 때문에 start === end인 경우도 파악해줘야 해서 start <= end라고 이해하는 것이 좋다. (그렇다면 start = mid이거나 end = mid로 하면 안되는 이유 -> 이거는 무한 루프다. 궁금하면 직접 확인해 보자!)

 

 

정리하면

이분 탐색으로 제한 시간을 구한다.

반복문을 돌리며 금만 구하는 경우의 금 갯수, 은만 구하는 경우의 은 갯수, 금은 적절히 구하는 경우의 총합 갯수를 파악한다.

저 세 가지가 구하고자 하는 금, 은, 금 + 은 갯수보다 크거나 같으면 제한 시간을 줄이고 반대의 경우 제한 시간을 늘려서 최소 시간을 구한다.

 

/*
시간복잡도 줄이기
시간기준 이분탐색?
dp 안됨. -> 최적해 보장? + 공간복잡도
그리디 안됨. -> 최소 보장 X
완전 탐색 안됨 -> 시간복잡도

판단하지 못한 부분 -> 각각의 트럭은 병렬로 움직인다.
*/

function solution(a, b, g, s, w, t) {
  const n = g.length;
  var answer = -1;

  let start = 0;
  let end = 10 ** 5 * 2 * (a + b); // 그냥 최대 시간으로 할 것

  while (start <= end) {
    const mid = Math.floor((start + end) / 2);

    // **반대로 풀기** 시간 고정
    // **생각하지 못한 부분**
    // 금만 채굴하는 경우, 은만 채굴하는 경우, 둘 다 적절히 채굴하는 경우
    // 안의 과정은 알 수 없으므로 이렇게 엣지 케이스를 구해서
    // 세 가지 경우에 모두 구할 수 있는 경우 -> true를 반환한다.
    let gold = 0;
    let silver = 0;
    let both = 0;

    for (let i = 0; i < n; i++) {
      // 1) 제한 시간 안에 채굴할 수 있는 최대 왕복 횟수 구하기
      let maxTimes = Math.floor(mid / (t[i] * 2));

      // 나머지가 편도 시간 보다 크다면 -> 왕복 횟수 + 1
      if (mid % (t[i] * 2) >= t[i]) maxTimes++;

      // 최대 무게 구하기
      const maxWeight = maxTimes * w[i];

      gold += Math.min(g[i], maxWeight);
      silver += Math.min(s[i], maxWeight);
      both += Math.min(g[i] + s[i], maxWeight);
    }

    if (gold >= a && silver >= b && both >= a + b) {
      answer = mid;
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }

  return answer;
}

 

AI한테 물어보면 너무 쉽게 답해주고 세부적인 거는 이해할 수 없어서 따로 적었다.

(나중에 복기하자)