이 문제에서는 정수 n이 주어졌을 때, 짝수 자리 숫자들의 합과 홀수 자리 숫자들의 합의 절대 차이가 1이 되는 모든 n자리 숫자를 출력해야 합니다. 단, 숫자를 생성할 때 맨 앞에 오는 0(선행 0)은 유효한 자릿수로 간주하지 않습니다.
절대 차이(absolute difference)란 두 수의 차이를 절댓값, 즉 항상 양수로 나타낸 값을 의미합니다.
예시를 통해 문제를 좀 더 구체적으로 살펴보겠습니다.
입력: n = 2 출력: 10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98 설명 : 출력 결과 중 하나의 숫자를 예로 들면, 54 → 짝수 자리 숫자 − 홀수 자리 숫자 = 5 − 4 = 1 89 → 짝수 자리 숫자 − 홀수 자리 숫자 = 8 − 9 = −1 , |−1| = 1
접근 방법
이 문제를 해결하려면 두 자릿수 합의 차이가 1 또는 −1이 되는 모든 n자리 숫자를 찾아야 합니다. 이를 위해 특정 자릿수에 가능한 모든 값을 하나씩 고정하고, 그 자리가 짝수 번째인지 홀수 번째인지에 따라 나머지 자릿수에 올 값을 재귀적으로 채워 나가면서 조건이 유지되도록 탐색합니다.
구현 예제
다음 프로그램은 위에서 설명한 해결 방법을 보여줍니다.
#include <iostream>
using namespace std;
void printNumber(int n, char* out, int index, int evenSum, int oddSum){
if (index > n)
return;
if (index == n){
if (abs(evenSum - oddSum) == 1) {
out[index] = ' ';
cout << out << " ";
}
return;
}
if (index & 1) {
for (int i = 0; i <= 9; i++) {
out[index] = i + '0';
printNumber(n, out, index + 1, evenSum, oddSum + i);
}
} else {
for (int i = 0; i <= 9; i++) {
out[index] = i + '0';
printNumber(n, out, index + 1, evenSum + i, oddSum);
}
}
}
int findNumberWithDifferenceOne(int n) {
char out[n + 1];
int index = 0;
int evenSum = 0, oddSum = 0;
for (int i = 1; i <= 9; i++) {
out[index] = i + '0';
printNumber(n, out, index + 1, evenSum + i, oddSum);
}
}
int main() {
int n = 3;
cout<<n<<" digit numbers with absolute difference 1 : \n";
findNumberWithDifferenceOne(n);
return 0;
}출력 결과
3 digit number with absolute difference 1 − 100 111 120 122 131 133 142 144 153 155 164 166 175 177 186 188 197 199 210 221 230 232 241 243 252 254 263 265 274 276 285 287 296 298 320 331 340 342 351 353 362 364 373 375 384 386 395 397 430 441 450 452 461 463 472 474 483 485 494 496 540 551 560 562 571 573 582 584 593 595 650 661 670 672 681 683 692 694 760 771 780 782 791 793 870 881 890 892 980 991
코드 동작 원리
위 코드는 재귀적 백트래킹(backtracking) 방식으로 동작합니다. 먼저 첫 번째 자리에는 1부터 9까지의 값을 넣어 선행 0이 등장하지 않도록 처리합니다. 이후 각 자리마다 0부터 9까지의 모든 숫자를 시도하면서, 현재 자리의 인덱스가 홀수이면 해당 값을 oddSum에, 짝수이면 evenSum에 누적합니다. 모든 자릿수가 채워지는 시점(index == n)에 두 합의 절대 차이가 정확히 1인 경우에만 완성된 숫자를 출력합니다.
이 방식은 조건을 만족하지 않는 조합을 조기에 가지치기할 수 있어, 단순히 모든 n자리 숫자를 일일이 검사하는 브루트포스 방식보다 효율적으로 동작합니다.