문제 설명
선행 0(leading zero)이 없는 숫자 N이 주어졌을 때, 인접한 두 자릿수를 서로 교환하는 연산을 반복하여 N을 25로 나누어 떨어지게 만들어야 합니다. 이때 필요한 최소 연산 횟수를 구하는 것이 목표입니다. 단, 연산 과정에서 어떤 시점에도 숫자 앞에 0이 위치해서는 안 됩니다. 아무리 교환해도 25의 배수를 만들 수 없다면 -1을 출력합니다.
예를 들어 N = 5071이라면, 다음과 같이 4번의 이동만으로 25의 배수를 만들 수 있습니다.
5071 → 5701 → 7501 → 7510 → 7150
참고로 어떤 수가 25의 배수가 되려면 마지막 두 자릿수가 반드시 00, 25, 50, 75 중 하나여야 한다는 점을 기억하면 접근 방식을 이해하는 데 도움이 됩니다.
알고리즘
- 숫자 내에서 가능한 모든 자릿수 쌍을 탐색합니다. 첫 번째 자릿수의 위치를 'i', 두 번째 자릿수의 위치를 'j'라고 합니다.
- 해당 두 자릿수를 숫자의 마지막 두 자리로 차례대로 옮깁니다.
- 이동 후 숫자 앞에 0이 있다면, 가장 왼쪽에 있는 0이 아닌 자릿수를 찾아 첫 번째 자리로 이동시켜 선행 0을 제거합니다.
- 최종적으로 만들어진 숫자가 25로 나누어 떨어진다면, 지금까지의 스왑 횟수와 비교하여 정답을 갱신합니다.
예제 코드
#include <iostream>
#include <algorithm>
#include <string>
#include <climits>
using namespace std;
int requiredMoves(long long n){
string str = to_string(n);
int ans = INT_MAX;
int len = str.size();
for (int i = 0; i < len; ++i) {
for (int j = 0; j < len; ++j) {
if (i == j)
continue;
string temp = str;
int cnt = 0;
// i번째 자릿수를 마지막 자리로 이동
for (int k = i; k < len - 1; ++k) {
swap(temp[k], temp[k + 1]);
++cnt;
}
// j번째 자릿수를 뒤에서 두 번째 자리로 이동
for (int k = j - (j > i); k < len - 2; ++k) {
swap(temp[k], temp[k + 1]);
++cnt;
}
// 선행 0 제거: 가장 왼쪽의 0이 아닌 자릿수를 맨 앞으로 이동
int pos = -1;
for (int k = 0; k < len; ++k) {
if (temp[k] != '0') {
pos = k;
break;
}
}
for (int k = pos; k > 0; --k) {
swap(temp[k], temp[k - 1]);
++cnt;
}
long long num = atoll(temp.c_str());
if (num % 25 == 0)
ans = min(ans, cnt);
}
}
if (ans == INT_MAX)
return -1;
return ans;
}
int main(){
int n = 5071;
cout << "Minimum required moves: " << requiredMoves(n) << endl;
return 0;
}출력 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.
Minimum required moves: 4
정리
이 풀이는 가능한 모든 자릿수 쌍을 대상으로 마지막 두 자리에 배치하는 경우를 시도하고, 각 경우마다 필요한 스왑 횟수를 계산한 뒤 그중 최솟값을 선택하는 완전 탐색(brute force) 방식입니다. 시간 복잡도는 자릿수 길이를 L이라 할 때 O(L²)개의 쌍을 검사하고 각각 O(L)번의 스왑을 수행하므로 O(L³)이며, 자릿수가 많지 않은 입력에서 충분히 효율적으로 동작합니다.