[PS] 99클럽 코테 스터디 23일차 TIL (마법의 엘리베이터)

문제

문제 링크

설명

엘리베이터를 타고 0층 으로 내려가는데 누를 수 있는 버튼은 10^c 로만 주어진다. 0층을 가는데 필요한 최소 버튼 횟수를 구하는 문제. 예를 들어 현재 층이 16 층이면 다음과 같은 경우들이 있다.

// 16층에서 0층을 가는 방법
// 1. 
-10, -10, +1, +1, +1, +1    ==> 버튼 여섯번 누르는 경우

// 2. 
-10, -1, -1, -1, -1, -1, -1    ==> 버튼 일곱번 누르는 경우

버튼을 최소로 누르는 횟수는 여섯번 이다.

시도한 방법

일단 +1 이나 -1 을 누르는 횟수를 최소화 해야 한다. 위 예시의 16 과 같은 경우엔 -1 을 여섯번 누루는 것보다 -10 을 한번 누른 후 +1 을 누르는 횟수가 더 적다는 것에 착안하면,

• 1의 자리 숫자가 5보다 큰 경우 올림을 해서 20으로 만들고 출발하는 것이 더 이득이다.
• 1의 자리 숫자가 5보다 작은 경우 그 숫자만큼 -1 혹은 +1 을 해줘야 한다.

올림에 필요한 수를 카운트해 answer 변수에 담고, storey 도 그만큼 늘려준다. 그 후 1의 자리를 제외한 숫자부터 다시 반복한다.

class Solution {
    public int solution(int storey) {
        int answer = 0;
        while (storey > 0) {
          int lastNum = storey % 10;
          if (lastNum > 5) {
            answer += (10 - lastNum);
            storey += (10 - lastNum);
          } else {
            answer += lastNum;
          }
          storey /= 10;
        }
        return answer;
    }
}

이대로 풀릴 줄 알았는데, 통과를 못하는 경우가 있어서 다시 생각해봤다. 예를 들어 54 인 경우 먼저 60을 만들고 출발할 지, 50을 만들고 출발할 지 생각해보면 -1 또는 +1 을 최소로 누르려면 54에서 가까운 50 으로 가는것이 더 유리하다. 그러나 65 의 경우 다음과 같이 생각해 볼 수 있다. 65는 올림하는게 유리하다

즉, 마지막 숫자가 5인 경우 올림이 유리한지 내림이 유리한지는 그 다음 숫자까지 확인해야 한다.

풀이 (그리디)

그리디 알고리즘 : 각 자리수마다 0을 만들기 위한 최적의 선택을 해야 한다.

[ 0, 1, 2, 3, 4, 5 ]   --> 그냥 -1 씩 빼는 게 유리
[ 6, 7, 8, 9 ]         --> +1 을 눌러 10을 만들고 -10 을 하는게 유리

class Solution {
    public int solution(int storey) {
        int answer = 0;
        while (storey > 0) {
          int lastNum = storey % 10;
          if (lastNum > 5 || (lastNum == 5 && (storey / 10) % 10 >= 5)) {
            answer += (10 - lastNum);
            storey += (10 - lastNum);
          } else {
            answer += lastNum;
          }
          storey /= 10;
        }
        return answer;
    }
}

마지막 숫자가 5인 경우엔 다음 숫자도 확인한다. 다음 숫자도 5 이상인 경우엔 올림이 유리하다.

풀이 (그리디 + DP)

올림, 내림의 경우를 적다보니 점화식이 발견된다. 올림과 내림 둘 중 최소값을 선택하면 되는데, 경우의 수를 판단하는 방식이 재귀적으로 수행된다. dp 나 dfs 로도 풀이가 가능할 것 같다.

f(65) = Math.min(5 + f(7), 5 + f(6)) 

점화식을 그대로 코드로 옮기면 아래와 같다. 10 이하의 수에 대해선 재귀함수로 처리할 필요 없이 바로 리턴한다.

top-down

class Solution {
  private final Map<Integer, Integer> memo = new HashMap<>();
  
  public int solution(int storey) {
    int answer;
    if (storey <= 5) {
      return storey;
    } else if (storey < 10) {
      return 11 - storey;
    }

    if (memo.containsKey(storey)) {
      return memo.get(storey);
    }
    
    int lastNum = storey % 10;
    int down = solution(storey / 10) + lastNum;
    int up = solution(storey / 10 + 1) + (10 - lastNum);
    
    answer = Math.min(down, up);
    memo.put(storey, answer);
    return answer;
  }
}

bottom-up

class Solution {
  public int solution(int storey) {

    int[] dp = new int[storey + 1];

    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;
    dp[4] = 4;
    dp[5] = 5;
    dp[6] = 5;
    dp[7] = 4;
    dp[8] = 3;
    dp[9] = 2;
    for (int i = 10; i <= storey; i++) {
      int lastNum = i % 10;
      dp[i] = Math.min(dp[i / 10 + 1] + (10 - lastNum), dp[i / 10] + lastNum);
    }
    return dp[storey];
  }
}

회고

그리디는 그 자체로 알고리즘이라고 하기 보다는 문제 풀이의 핵심 아이디어이고, 그걸 이용해 풀이하는 방식은 여러가지로 가능하다는 것을 느꼈다.