[코드업] 3120 : 리모컨 (C)

알고리즘

그리디, 백트래킹

힌트

매 시행마다 목표 채널과 현재 채널중 큰 것을 골라 빼거나 작은 것을 골라 더한다.

 

풀이

a와 b의 대소 관계가 고정되어 있지 않기 때문에 임의로 a>b로 잡아 주었다.

변경할 수 있는 수가 1, -1, 5, -5, 10, -10 인 것에 주목하자. (절대값이 같은 두 수가 3쌍이다.)

a에 10을 뺀 것은 b에 10을 더한 것으로 치환할 수 있다.

( 현재 온도를 x도 높인 것은 목표 온도를 x도 낮춘것 과 같고, 현재 온도를 x도 낮춘 것은 목표 온도를 x도 높인 것 과 같다. )

따라서 두 수 중 큰 수만 값을 줄여주면 되기 때문에

임의로 a와 b의 대소관계를 정해주는 것은 일반성을 잃지 않는다. 시행 횟수에 영향을 미치지 않는다.

d 배열에 양수 값만 필요하고 a, b 두 수의 차에 d[i]를 뺀 값의 절대값이 가장 크도록 하는 i를 찾은 뒤

a (두 수중 더 큰수)에 빼 d[i]를 빼주면 된다.

이 시행을 a와 b가 같아질 때 까지 반복한다.

#include<iostream>
#include<cmath>
using namespace std;

int main(){
    int d[3]={1,5,10};

    int a,b,cnt=0;
    cin>>a;
    cin>>b;

    while(a!=b){

        if(a<b){
            int tmp=a;
            a=b;
            b=tmp;
        }

        int result=a-b,index;
        for(int i=0;i<3;i++){
            if(abs(a-b-d[i])<result){
                result=abs(a-b-d[i]);
                index=i;
            }
        }
        a-=d[index];
        cnt++;        
    }        
    cout<<cnt;
}