[8주차_금요일] 에어컨

[baexxbin]

• 사이트 : 프로그래머스(PG)
• 문제: 에어컨
• 번호: 214289
• 레벨: Level3

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[KodaHye]

🤔 시간복잡도 고려사항

승객이 탑승 중인 시간에 쾌적한 실내온도를 유지하기 위한 최소 소비전력 구하기

• 2 <= onboard <= 1,000 이기 때문에 승객이 타 있는 시간에 에어컨 온도 내림, 유지, 올림 모든 경우를 고려한다면 최대 3^1000가지 경우의 수가 나올 것이라고 생각함 → 시간 초과 onboard배열의 크기를 고려하여 시간 내에 문제 풀이할 수 있는 방법 생각해야 됨 → DP

💡 풀이 아이디어

• 문제에서 외부 온도 & 희망 온도가 나와 있지만, 실질적으로 고려해야되는 것은 1. 외부온도와 내부온도가 같냐 / 다르냐, 2. 온도 변화 처리를 고려해야 됨
  • 외부온도와 내부온도 동일 여부에 따라 온도 변화 처리에 대한 비용이 달라지기 때문

1. t1, t2, temperature 값 재조정
   • 에어컨을 트는 행위를 온도를 올리거나 유지하는 행위로 단순화하기 위해 temperature값을 재조정
   • dp 배열에서 인덱스 확인을 할 수 있도록 외부 온도를 0으로 설정하고, 0도에서 t2도 까지 확인하도록 함
2. dp배열 채워주기
   • 외부 온도와 비교하며, 온도 유지, 하강, 상승 중 어떤 것을 할지 고르고 최소 비용 구해주기

문제가 잘 안풀려서 가장 이해가 잘 되는 풀이를 보면서 문제랑 풀이 둘 다 이해해보려고 했는데요 ,,, 완벽하게 이해되지는 않네요 ㅠㅠ!!,,,

• 이해 안되는 부분 1) 처음 temperature 값 재조정 과정
• 이해 안되는 부분 2) dp배열 열의 크기를 t2 +1이 아닌 t2 + 2로 해야되는 이유
• 이해 안되는 부분 3) 다른 풀이도 봐봤는데, 직관적으로 와닿는 풀이가 없음,,,,

헝헝헝,,,,,, 문제가 잘 안풀리니까 우울하네요 문제 풀이 기깔나게 해 주실 스피드웨건 구해요,,,,,,,,,,,,,,,,, 그리디, DP 어렵다ㅇ아악ㄱㄱ1!!!!!!! 😱

참고 블로그

[Jewan1120]

🤔 시간복잡도 고려사항

• 2 ≤ onboard의 길이 ≤ 1,000
• -10 ≤ temperature ≤ 40
• 1,000 x 50 = 5 x 10^4 → O(N^2) 가능

💡 풀이 아이디어

• 조합 문제라고 생각 → 재귀, 백 트래킹
  • 각 깊이마다 최적의 온도를 찾아주면 되는 줄 알았음! → 시간초과
• DP로 변환해서 풀이
• int[][] dp = new int[onboard.length][51];
  • dp[i][j]: i번째 깊이에서 j온도를 만드는 최소 전력값
• 사람이 탔을 때 적절한 온도가 아니라면 잘못된 값이므로 스킵

  // 사람이 탔을 때, 적절한 온도가 아니라면 스킵
  if (onboard[i] == 1 && !isPossible(j, t1, t2)) {
    continue;
  }

• i깊이의 j번째 온도에서 다음 깊이i+1의 온도를 결정해줘야 함
  1. 에어컨을 사용하지 않았을 때
     • 현재 온도가 외부 온도와 다를 때, 상황에 따라 증감
     • 현재 온도와 외부 온도가 같다면 그대로
  2. 에어컨을 사용했을 때
     • 현재 온도에서 +1, -1, 0 전부 계산

       if (onboard[i] == 1 && !isPossible(j, t1, t2)) {
       continue;
       }
       // 에어컨을 가동하지 않았을 때
       if (j < temperature && j < 50) {
       dp[i + 1][j + 1] = Math.min(dp[i + 1][j + 1], dp[i][j]);
       } else if (j > temperature && j > 0) {
       dp[i + 1][j - 1] = Math.min(dp[i + 1][j - 1], dp[i][j]);
       } else {
       dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j]);
       }
       // 에어컨을 가동했을 때
       if (j > 0)
       dp[i + 1][j - 1] = Math.min(dp[i + 1][j - 1], dp[i][j] + a);
       if (j < 50)
       dp[i + 1][j + 1] = Math.min(dp[i + 1][j + 1], dp[i][j] + a);
       dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + b);

• dp배열이 완성되었다면 가능한 값들 중 최솟값 찾기

  int min = INF;
  for (int i = 0; i < 51; i++) {
    // 가능한 값들 중 최솟값 찾기
    if (onboard[len - 1] == 1 && !isPossible(i, t1, t2)) 
        continue;
    min = Math.min(min, dp[len - 1][i]);
  }

세상에... 처음에 재귀로 방향 잘못 잡아서 한참 걸렸습니다.. 재밌는 문제였네요. 근데 왜 dp값 결정할 때, 현재 값을 결정하면 틀리고 다음 값을 결정하는 방식으로 하면 맞을까요... 의문

[baexxbin]

🤔 시간복잡도 고려사항

• -10 ≤ temperature ≤ 40 (50)
• 2 ≤ onboard의 길이 ≤ 1,000
• 완전탐색 가능

💡 풀이 아이디어

• dp 떠올림
  • 점화식과 테이블을 어떻게 구성할지 잘 몰라서 패쓰함..
• 완전탐색 그리디 떠올림
  • 뭘 기준으로 돌릴지 애매함
  • t1~t2 사이값을 다돌려볼까도 생각했으나 해당 값은 의미 없는 값이라고 판단..

해설을 참고해 dp로 돌아옴

• DP (bottom-up)
  • 초기 설정
  • 사용자 탑승시엔 무조건 t1~t2사이 값이여야하기에 값 조정

    참고한 개념에선 이게 중요한 요소로 이용한 것 같았는데 최종 코드에선 딱히 큰 역할은 안하는듯...

  • dp[i][j] = k : i분에 j도로 만들 수 있는 최소 전력 k
    • i분에 j값 만들기
    • 직전 시간(i-1) j-1에서 1도 올리기
    • 직전 시간(i-1) j+1에서 1도 내리기
    • 직전 시간(i-1) j에서 j도 유지하기

// 온도를 1도 낮추기
if (j > 0) {
    int cost = (j - 1 < temperature) ? a : 0; // 외부온도보다 낮출 온도가 낮아서 온도조절이 필요하면 a비용 들어감
    dp[i + 1][j - 1] = Math.min(dp[i + 1][j - 1], dp[i][j] + cost);     // 그 다음 시간에 온도를 내린 비용은, 기존 최소 비용과 현재 최소 전력비용에 cost더한 값 중 작은 값
}

// 온도를 유지
int stayCost = (j == temperature) ? 0 : b; // 에어컨 끈 상태에서 비용
dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + stayCost);             // 이전에 계산한 기존 비용 vs 온도 유지시 비용

// 온도를 1도 높이기
if (j < 50) {
    int cost = (j + 1 > temperature) ? a : 0; // 외부온도보다 높일 온도가 높아서 온도조절이 필요하면 a비용 들어감
    dp[i + 1][j + 1] = Math.min(dp[i + 1][j + 1], dp[i][j] + cost);     // 그 다음 시간에 온도를 올린 비용은, 기존에 계산해놓은 비용과 현재 온도를 높인 비용 중 최소 값
}

해설... 기대하겠습니다 엇 저도 dp[i][j]를 기준으로 점화식을 이어가고 싶었는데....! 의문입니다,,

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: DP
• 시간복잡도: 2 ≤ onboard의 길이 ≤ 1,000 적정온도 -10 ≤ t1 < t2 ≤ 40

💡 풀이 아이디어

특정 시간의 특정 온도일 때 필요한 최소 전력 찾기

• 특정 시간은 onboard 길이만큼 있으며 "onboard[i]가 1이라면 i분에 승객이 탑승 중" 을 의미
  1. 손님이 있을 때 적정온도가 아닐 경우는 제외하고 메모이제이션 진행
  2. 에어컨 ON/OFF 와 실외온도 에 따른 전체 6가지 케이스가 존재

     
     에어컨 ON

• 온도 유지 > b 에너지 소비
• 온도 내림 > a 에너지 소비
• 온도 올림 > a 에너지 소비

에어컨 OFF

• 온도 유지 > 0 에너지 소비
• 실외온도 보다 현재 온도가 높을 때 온도 내림 > 0 에너지 소비
• 실외온도 보다 현재 온도가 낮을 때 온도 올림 > 0 에너지 소비

  
  3. 현재의 값으로 다음 값을 저장하는 `Bottom-up` 방식으로 진행
  **현재 온도에 따라 다음의 온도를 내릴지, 올릴지 변경 되므로 `Bottom-up` 방식**으로 메모이제이션 

4. 에어컨 ON 일 때는 다음의 온도를 내릴지, 올릴지 모르기 때문에 3가지 경우 모두 메모이제이션
5. 에어컨 OFF 일 때는 실외온도를 기준으로 다음 온도가 결정되기 때문에 1가지 경우만 메모이제이션