문제 개요
두 숫자 a와 b가 있다고 가정해 봅시다. Amal은 항상 TV 볼륨을 'b' 값으로 설정하지만, 어느 날 Bimal이 볼륨을 'a' 값으로 변경해 버렸습니다. 리모컨에는 여섯 개의 버튼(-5, -2, -1, 1, 2, 5)이 있으며, 이 버튼들을 사용하면 볼륨을 1, 2 또는 5씩 증가시키거나 감소시킬 수 있습니다. 볼륨 값은 매우 클 수 있지만 음수가 될 수는 없습니다.
우리는 Amal이 볼륨을 다시 'b'로 맞추기 위해 눌러야 하는 최소 버튼 클릭 횟수를 구해야 합니다.
예를 들어 입력이 a = 5, b = 14라면 출력은 3이 됩니다. +5 버튼을 한 번 눌러 10으로 만든 뒤, +2 버튼을 두 번 눌러 14에 도달하기 때문입니다.
풀이 접근 방식
이 문제는 그리디(greedy) 방식으로 간단하게 해결할 수 있습니다. 먼저 두 볼륨 값의 차이의 절댓값을 구한 후, 가능한 한 큰 단위인 5부터 사용하고, 남은 나머지는 2와 1의 조합으로 처리하는 것이 최적의 전략입니다.
차이를 d라고 할 때, 필요한 최소 클릭 수는 다음과 같이 계산됩니다.
d := |a - b| return (d / 5 + (d mod 5 + 1) / 2)
여기서 d / 5는 5 단위 버튼을 누르는 횟수이고, (d % 5 + 1) / 2는 남은 나머지 값을 2와 1 버튼으로 처리하는 데 필요한 횟수입니다. 나머지가 0이면 추가 클릭이 필요 없고, 1이면 1번, 2면 1번, 3이면 2번, 4면 2번의 클릭이 필요합니다.
C++ 구현 예제
아래 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(int a, int b){
int d = abs(a - b);
return (d / 5 + (d % 5 + 1) / 2);
}
int main(){
int a = 5;
int b = 14;
cout << solve(a, b) << endl;
}입력
5, 14
출력
3