각 자릿수가 배열의 요소로 저장되어 있을 때, 이 배열이 나타내는 수에 1을 더하는 문제입니다. 배열은 음수가 아닌 숫자들로 구성되며, 가장 큰 자릿수(최상위 자릿수)가 배열의 첫 번째 요소에 위치합니다.
1을 더하는 알고리즘 단계
배열의 끝에서부터 살펴보며, 마지막 자릿수가 9보다 작으면 단순히 1을 더해 줍니다 (예: 4 → 5).
마지막 요소가 9라면 해당 값을 0으로 바꾸고 올림수(carry)를 1로 설정합니다.
다음 반복에서 올림수를 확인하고, 자릿수에 더했을 때 10이 되면 위와 동일한 과정을 반복합니다.
올림수를 더한 후에는 다음 반복을 위해 올림수를 0으로 초기화합니다.
모든 자릿수에서 올림이 발생하여 배열의 크기를 늘려야 하는 경우, 맨 앞에 1을 추가합니다.
예를 들어 배열이 [7, 6, 3, 4]라면 이 배열은 십진수 7634를 나타냅니다. 여기에 1을 더하면 7635가 되므로, 새로운 배열은 [7, 6, 3, 5]가 됩니다.
예시
입력: [7, 6, 9, 9]
출력: [7, 7, 0, 0]
입력: [4, 1, 7, 8, 9]
출력: [4, 1, 7, 9, 0]
설명: 배열의 마지막 요소에 1을 더합니다. 만약 그 값이 9보다 작다면 연산은 여기서 끝납니다. 하지만 값이 9라면 해당 자릿수를 0으로 만든 뒤, 앞쪽에 남은 자릿수들에 대해 재귀적으로 같은 연산을 수행합니다. 이렇게 하면 올림이 필요한 만큼 앞자리로 전파되어 자연스럽게 처리됩니다.
C++ 구현 예제
#include <iostream>
using namespace std;
void sum(int arr[], int n) {
int i = n;
if(arr[i] < 9) {
arr[i] = arr[i] + 1;
return;
}
arr[i] = 0;
i--;
sum(arr, i);
if(arr[0] > 0) {
cout << arr[0] << ", ";
}
for(int i = 1; i <= n; i++) {
cout << arr[i];
if(i < n) {
cout << ", ";
}
}
}
int main() {
int n = 4;
int arr[] = {4, 1, 7, 8, 9};
sum(arr, n);
return 0;
}
위 코드를 실행하면 배열 [4, 1, 7, 8, 9]에 1을 더한 결과인 4, 1, 7, 9, 0이 출력됩니다. 마지막 자릿수 9가 0으로 바뀌고, 올림이 앞자리 8에 전달되어 9가 된 것을 확인할 수 있습니다.