이 문제에서는 하나의 숫자가 주어지며, 이 숫자에서 딱 한 자릿수를 제거해야 합니다. 제거한 뒤 새로 만들어진 숫자가 6으로 나누어 떨어지도록 하는 것이 목표이고, 그때 제거한 자릿수의 위치를 출력해야 합니다.
예시를 통해 개념을 살펴보겠습니다.
입력 : 1324
출력 : 4
설명 — 4번째 자릿수 '4'를 제거하면 132가 되고, 132는 6으로 나누어 떨어집니다.
즉, 주어진 숫자에서 어느 위치의 자릿수를 제거해야 6의 배수가 되는지 그 위치를 반환하는 것이 핵심입니다.
문제 해결의 핵심 원리
이 문제를 풀기 위해서는 다음과 같은 수학적 성질을 활용합니다.
어떤 수가 2와 3으로 모두 나누어 떨어지면, 그 수는 6으로도 나누어 떨어진다.
따라서 자릿수를 하나 제거한 뒤 만들어진 새로운 숫자가 2의 배수 조건과 3의 배수 조건을 동시에 만족하는지만 확인하면 됩니다.
접근 방법
주어진 숫자의 마지막 자릿수에 따라 두 가지 경우로 나누어 생각할 수 있습니다.
1. 마지막 자릿수가 홀수인 경우
새로 만들어진 숫자가 2의 배수가 되려면 일의 자리가 짝수여야 하므로, 마지막 자릿수가 홀수라면 유일한 방법은 마지막 자릿수를 제거하는 것입니다. 이때 마지막에서 두 번째 자릿수가 짝수이고, 나머지 자릿수들의 합이 3의 배수일 때만 6으로 나누어 떨어집니다. 그렇지 않다면 해답은 존재하지 않습니다(-1 반환).
2. 마지막 자릿수가 짝수인 경우
마지막 자릿수가 짝수라면 숫자 전체를 3으로 나눈 나머지를 구하고, 그 결과에 따라 제거할 수 있는 자릿수가 결정됩니다. 숫자를 3으로 나눈 나머지는 세 가지 경우로 나뉩니다.
- 나머지가 1인 경우 — 자릿값의 합에서 1, 4, 7 중 하나를 제거하면 됩니다. 제거 가능한 자릿수가 여러 개라면, 제거 후 만들어지는 숫자가 가장 커지도록 선택합니다.
- 나머지가 2인 경우 — 2, 5, 8 중 하나를 제거하면 됩니다. 마찬가지로 여러 개가 가능하다면 결과 숫자가 최대가 되도록 고릅니다.
- 나머지가 0인 경우 — 3, 6, 9 중 하나를 제거하면 됩니다. 이 경우에도 결과 숫자가 최대가 되는 위치를 우선적으로 선택합니다.
예제 풀이
마지막 자릿수가 홀수인 경우
1) 34241341
이 경우 제거할 수 있는 유일한 자릿수는 마지막 위치의 '1'입니다. 이를 제거하면 3424134가 되고, 이는 6으로 나누어 떨어집니다. 따라서 제거한 자릿수의 위치인 8을 반환합니다.
2) 3214241
이 경우에도 제거할 수 있는 것은 마지막 위치의 '1'뿐입니다. 제거하면 321424가 되는데, 이는 6으로 나누어 떨어지지 않습니다. 따라서 -1을 반환합니다.
마지막 자릿수가 짝수인 경우
8097860
각 자릿수의 합은 38이고, 38을 3으로 나눈 나머지는 2입니다. 나머지가 2이므로 2, 5, 8 중 하나를 제거할 수 있습니다. 이 숫자에서 8은 1번째 위치와 5번째 위치에 있습니다. 1번째 위치의 8을 제거하면 097860처럼 앞자리가 줄어들어 더 작은 수가 되므로, 결과 숫자를 최대화하기 위해 5번째 위치의 8을 제거합니다. 그러면 809760이 되고, 이는 6으로 나누어 떨어집니다. 따라서 5를 반환합니다.
C++ 구현
위의 로직을 바탕으로 문제를 해결하는 프로그램을 작성해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void isDivisibleBy6(string num){
int n = num.length();
int a[n];
int sum = 0;
for (int i = 0; i < n; i++) {
a[i] = num[i] - '0';
sum += a[i];
}
if (a[n - 1] % 2){
if ( (a[n - 2] % 2 != 0) || (sum - a[n - 1]) % 3 != 0) {
cout << "-1" << endl;
}
else {
cout << n << endl;
}
}
else {
int re = sum % 3;
int del = -1;
int flag = 0;
for (int i = 0; i < n - 1; i++) {
if ((a[i]) % 3 == re) {
if (a[i + 1] > a[i]) {
del = i;
flag = 1;
break;
}
else {
del = i;
}
}
}
if (flag == 0) {
if (a[n - 2] % 2 == 0 and re == a[n - 1] % 3)
del = n - 1;
}
if (del == -1)
cout << -1 << endl;
else {
cout << del + 1 << endl;
}
}
}
int main(){
string number = "343224152";
isDivisibleBy6(number);
return 0;
}
출력
5
코드 설명
이 프로그램의 동작 과정은 다음과 같습니다.
- 입력받은 숫자를 문자열로 처리한 뒤, 각 자릿수를 정수 배열로 변환하고 자릿수의 합을 계산합니다.
- 마지막 자릿수가 홀수인 경우 — 마지막 자릿수를 제거했을 때의 조건(앞 자릿수가 짝수이고, 나머지 자릿수의 합이 3의 배수)을 검사해 조건을 만족하면 마지막 위치 n을, 아니면 -1을 출력합니다.
- 마지막 자릿수가 짝수인 경우 — 전체 합을 3으로 나눈 나머지(re)와 같은 나머지를 가진 자릿수를 찾습니다. 이때 바로 다음 자릿수가 현재 자릿수보다 큰 위치를 발견하면 그곳을 제거 대상으로 확정해 결과 숫자를 최대화합니다.
- 적절한 자릿수를 찾지 못하면 -1을, 찾았다면 해당 위치(del + 1)를 출력합니다.
이처럼 2와 3의 배수 판정 규칙만 잘 활용하면, 실제로 나눗셈을 반복하지 않고도 O(n) 시간 복잡도로 문제를 효율적으로 해결할 수 있습니다.