[PS/그리디/코드업] 3120 : 리모컨

컴퓨터실에서 수업 중인 정보 선생님은 냉난방기의 온도를 조절하려고 한다.
냉난방기가 멀리 있어서 리모컨으로 조작하려고 하는데, 리모컨의 온도 조절 버튼은 다음과 같다.
1) 온도를 1도 올리는 버튼
2) 온도를 1도 내리는 버튼
3) 온도를 5도 올리는 버튼
4) 온도를 5도 내리는 버튼
5) 온도를 10도 올리는 버튼
6) 온도를 10도 내리는 버튼
이와 같이 총 6개의 버튼으로 목표 온도를 조절해야 한다.
현재 설정 온도와 변경하고자하는 목표 온도가 주어지면 이 버튼들을 이용하여 목표 온도로 변경하고자 한다.
이 때 버튼 누름의 최소 횟수를 구하시오.
(예를 들어, 7도에서 34도로 변경하는 경우,
7 -> 17 -> 27 -> 32 -> 33 -> 34
이렇게 총 5번 누르면 된다.)

입력 : 현재 온도a 와 목표 온도b가 입력된다. ( 0 <= a , b <= 40 )
ex : 7 34

출력 : 최소한의 버튼 사용으로 목표온도가 되는 버튼의 횟수를 출력한다.
ex : 5

처음 문제를 봤을때, 거스름돈 문제가 생각났다.
거슬러 줘야할 동전의 최소 갯수를 구하는 알고리즘을 응용하면 쉽게 풀수 있을 것 같은 느낌!
처음 막 짜본 코드는 다음과 같다.

#include <iostream>

using namespace std;

int main() {

    int curT, objT, i, j = 0;
    cin >> curT >> objT;

    int button[6] = {10, -10, 5, -5, 1, -1};

    if (objT - curT >= 0) {
        i = 0;
        for (; i < 6; i += 2) {
            for (; curT + button[i] <= objT; j++) {
                curT += button[i];
            }
        }
    } else {
        i = 1;
        for (; i < 7; i += 2) {
            for (; curT + button[i] >= objT; j++) {
                curT += button[i];
            }
        }
    }
    cout << j;
    return 0;
}

현재 온도를 높이거나 내릴때 button[i]보다 높거나 낮을경우, 다음 버튼을 사용하는 식이다.
하지만..이 알고리즘은 문제가 있었으니...

띠용....o_O???

예를들어 현재 온도가 22도 이고, 목표 온도가 3도라고 하자.
내 알고리즘 대로라면

22-10 = 12
12-10 = 2 < 3이므로 버튼을 바꾼다.
12 - 5 = 7
7 - 5 = 2 < 3 이므로 버튼을 바꾼다.
5-1 = 4
4-1 = 3

이 과정은 총 6번 버튼을 눌러야 한다. 하지만 보시다시피 정답은 3번이다.
...? 아!!! 온도를 올리거나 내릴수 있었지!!!ㅜㅠ

22 - 10 = 12
22 - 10 = 2
2 + 1 = 3

기초 100제를 풀때까지만해도 앉아서 머리좀 굴리다보면 풀렸는데, 이번엔 그렇지 않았다. 

성공률 31.7%. 쉽지 않네여

밍...그냥 추우면 추운대로 더우면 더운대로 살것이지...나도 에어컨 안틀고사는데..

음 그래요 어쨌든 문제는 풀어야 하니까....
문제의 4번째 테스트케이스를 한번 자세히 살펴보자.

22도에서 3도로 온도를 낮추려면 19도를 낮추면 된다.
즉 19를 요리조리 빼고 더해서 0으로 만들면 된다.
한번씩 모든 버튼을 눌러보면 뭔가 규칙성이 보이지 않을까 싶어서 쭉 나열해 보았다.

19  -10 = 9
      -5 = 14
      -1 = 18
0과 가장 가까운 값을 다음값으로 취하면,
9 -10 = -1
    -5 = 4
    -1 = 7
마찬가지로 0과 가장 가까운 값을 다음값으로 취하면,
-1 +10 = 9
     +5 = 4
     +1 = 0

즉, 낮추거나 높여야 할 온도를 10,5,1과 각각 더하거나 뺐을때 그 결과가 0과 가장 가까운 값을 취하면 되지 않을까?

7도에서 34도의 경우도 다시한번 돌아보자.
7도에서 34도로 높이려면 34-7 = 27. 27을 0으로 만들면 된다.

27 - 10 = 17 ✔️
      - 5 = 22
      -1 = 26
17 - 10 = 7 ✔️
      - 5 = 12
      -1 = 16
7 - 10 = -3
     - 5 = 2 ✔️
     -1 = 6
2 - 10 = -8
    -5 = -3
    -1 = 1 ✔️
1 - 10 = -9
    -5 = -4
    -1 = 0 ✔️

띠용...! 5번만에 0이 될수 있었다.

코드로 어떻게 구현할수 있을까 생각하던 중 결과가 0에 가까운 값을 취하고 난 후에
그 수가 음수인지 양수인지 판단을 해야 다음에 더하던가 빼던가 할텐데 라는 생각이 들었다.

..?잠깐, 어차피 -1에서 +1을 하던가, +1에서 -1을 하던가.
더할수 있는 수는 정해져있고, 마침 부호도 서로 전부 반대이다.
즉, 결과값에서 절대값을 취해 주구장창 빼기면 하면..?

 

그리고 알고리즘이 반복되니 재귀함수를 쓰면 딱이겠다는 판단이 들었다.

#include <iostream>

using namespace std;

int button[] = {10, 5, 1};

int abs(int n) {
    if (n < 0)return -n;
    return n;
}

int findCnt(int value) {
    if (value == 0)return 0;
    int min = 40, tmp = 0;
    for (int i = 0; i < 3; i++) {
        tmp = value - button[i];
        if (min > abs(tmp)) min = abs(tmp);
    }
    return 1 + findCnt(min);
}

int main() {
    int curT, objT;
    cin >> curT >> objT;
    cout << findCnt(abs(curT - objT));
    return 0;
}

 

짜잔!

문제를 풀고 이분 저분의 해답을 찾아보는데,  이 문제는 그리디, DP, 백트래킹 으로 풀수 있다고들 말씀하신다.