[JS] 에어컨

쉽지 않은 문제였다...

 

dp로 풀면 뭔가 될꺼 같은데 1시간정도 넘게 고민을 해도 뭔가나올듯 말듯 했다. 그러다가 힌트만 참고하잔 생각으로 질문게시판을을 봤는데 dp를 2차원으로 쓴다는 말만 보고 아이디어를 얻고 혼자 생각해보았다.

 

오랜만에 난이도있는 dp문제를 접해서인지 dp를 2차원으로 둘 생각을 못했다!!

 

최대 1000초의 시간이 주어지고 온도도 50도 안으로 오니 가능했었던 문제였다.

 

 

만약 첫번째 예시를 통해서 dp를 채우면 아래와 같이 나와야 한다.

 

 

 

 

N은 편의상 INF중에서 N만 쓴것으로 무한대를 의미한다!

 

손님이 없다면 모든 경우의 수를 보고 있다면 희망온도 안에서만 경우의 수를 따지면 된다.

 

 

이때 생각해야할 것이있다.

 

1. 에어컨을 1도 올리는 경우

2. 에어컨을 1도 내리는 경우

3. 에어컨을 유지하는경우

4. 에어컨을 끄는 경우

 

 

나는 네가지 중에서 가장 작은 값을 골라 dp를 채우면 될 것이라 생각했다.

 

 

 

// 1번 풀이
function solution(temperature, t1, t2, a, b, onboard) {
  const dp = Array.from(Array(onboard.length), (x) => Array(50).fill(Infinity));

  temperature = temperature > t2 ? t1 - (temperature - t2) : temperature;
  temperature += 10;
  t1 += 10;
  t2 += 10;

  dp[0][temperature] = 0;

  // console.log(temperature,t1,t1,a,b)

  for (let i = 1; i < onboard.length; i++) {
    const isPersonInCar = onboard[i];
    for (let j = 0; j < 50; j++) {
      if (isPersonInCar && (j < t1 || j > t2)) continue;

      const candidates = [];
      candidates.push(j > 0 ? dp[i - 1][j - 1] + a : Infinity);
      candidates.push(dp[i - 1][j] + b);
      candidates.push(j < 49 ? dp[i - 1][j + 1] + a : Infinity);

      const dj = j > temperature ? 1 : j === temperature ? 0 : -1;
      if (0 <= j + dj && j + dj < 50) {
        candidates.push(dp[i - 1][j + dj]);
      }

      dp[i][j] = Math.min(...candidates);
    }
    console.log(dp[i]);
  }

  return Math.min(...dp[dp.length - 1]);
}

 

위처럼 했더니 주어진 테스트 케이스는 모두 통과했지만 실제 문제의 통과는 하지 못했다.

 

 

아마 1,2,3,4 번 중에서 온도가 내려가거나 올라갈때 문제가 생긴 것같았다.. 그렇게 계속 고민하다가

 

질문게시판을 한번 쓱 더 봤는데 온도를 무조건 올리거나 내리는것으로 고정한 다음에 문제를 푸는 방법이 있다는 글을봐서 이를 활용해 수정해봤더니 문제가 해결되었다.

 

function solution(temperature, t1, t2, a, b, onboard) {
  const dp = Array.from(Array(onboard.length), (x) => Array(50).fill(Infinity));

  temperature = temperature > t2 ? t1 - (temperature - t2) : temperature;
  t1 -= temperature;
  t2 -= temperature;
  temperature = 0;

  dp[0][temperature] = 0;
  console.log(temperature, t1, t2);

  for (let i = 1; i < onboard.length; i++) {
    const isPersonInCar = onboard[i];
    for (let j = 0; j < 50; j++) {
      if (isPersonInCar && (j < t1 || j > t2)) continue;

      const candidates = [];

      candidates.push(j > 0 ? dp[i - 1][j - 1] + a : Infinity);
      candidates.push(j !== 0 ? dp[i - 1][j] + b : dp[i - 1][j]);
      candidates.push(j < 49 ? dp[i - 1][j + 1] : Infinity);

      dp[i][j] = Math.min(...candidates);
    }
    // console.log(dp[i])
  }

  return Math.min(...dp[dp.length - 1]);
}

 

 

 

결국 해결하긴 했지만 자력으로 50%정도밖에 풀지 못한거 같아 많이 아쉬운 문제였다.