개요
이 글에서는 두 가지 연산만을 허용하여 숫자 m을 n으로 변환할 때 필요한 최소 연산 횟수를 구하는 프로그램을 C++로 작성해 보겠습니다.
두 개의 정수 m과 n이 주어졌을 때, 아래에 나열된 연산을 가장 적은 횟수로 사용하여 m을 n으로 바꾸는 것이 목표입니다.
허용된 연산
- 주어진 숫자에 2를 곱한다
- 주어진 숫자에서 1을 뺀다
접근 방법
m에서 출발해 n을 만드는 대신, 역으로 n에서 m을 향해 거꾸로 진행하면 문제가 훨씬 단순해집니다.
- n이 홀수인 경우 → 정방향에서 마지막 연산이 '−1'이었음을 의미하므로, n에 1을 더해 한 단계 되돌아갑니다 (연산 1회 소모)
- n이 짝수인 경우 → 정방향에서 마지막 연산이 '×2'였음을 의미하므로, n을 2로 나누어 되돌아갑니다 (연산 1회 소모)
- n이 m보다 작아진 경우 → 남은 차이(m − n)만큼 '−1' 연산을 반복하면 됩니다
- m ≤ 0이면서 n > 0인 경우 → 어떤 방법으로도 변환이 불가능하므로 −1을 반환합니다
짝수일 때마다 나누기를 우선적으로 적용하는 이러한 그리디(greedy) 방식은 항상 최소 연산 횟수를 보장합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 필요한 최소 연산 횟수를 구하는 함수
int convert(int m, int n){
if (m == n)
return 0;
if (m > n)
return m - n;
// 이 경우에는 변환 불가능
if (m <= 0 && n > 0)
return -1;
// n이 크고 홀수인 경우
if (n % 2 == 1)
// 역방향으로 '+1' 수행
return 1 + convert(m, n + 1);
// n이 짝수인 경우
else
// 역방향으로 '/2' 수행
return 1 + convert(m, n / 2);
}
int main(){
int m = 5, n = 11;
cout << "Minimum number of operations : " << convert(m, n);
return 0;
}
출력 결과
Minimum number of operations : 5
동작 과정 살펴보기
m = 5, n = 11인 경우 알고리즘은 다음과 같이 진행됩니다.
- 11은 홀수 → +1 하여 12로 이동 (1회)
- 12는 짝수 → ÷2 하여 6으로 이동 (2회)
- 6은 짝수 → ÷2 하여 3으로 이동 (3회)
- 이제 n(3)이 m(5)보다 작으므로, 차이인 2만큼 추가 연산 필요 (총 5회)
정방향으로 확인하면 실제 변환 경로는 5 → 4 → 3 → 6 → 12 → 11이며, 정확히 5번의 연산으로 목표를 달성함을 알 수 있습니다.