C++로 판별하는 덧셈 숫자(Additive Number) 문제 풀이

문제 개요

'0'부터 '9'까지의 숫자만으로 구성된 문자열이 주어졌을 때, 이 문자열이 덧셈 숫자(Additive Number)인지 판별하는 함수를 작성해야 합니다. 덧셈 숫자란 문자열의 자릿수들이 하나의 덧셈 수열을 이룰 수 있는 문자열을 의미합니다.

유효한 덧셈 수열은 최소 세 개의 숫자를 포함해야 하며, 첫 두 숫자를 제외한 나머지 모든 숫자는 바로 앞에 있는 두 숫자의 합과 같아야 합니다. 예를 들어 입력이 "112358"이라면 결과는 true입니다. 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8처럼 수열이 성립하기 때문입니다.

해결 접근 방법

이 문제는 재귀 호출과 백트래킹 기법을 활용하면 효율적으로 해결할 수 있습니다. 단계별 풀이 과정은 다음과 같습니다.

s, index, prev1, prev2를 매개변수로 받는 ok() 메서드를 정의합니다.
index가 문자열 s의 크기 이상이면 true를 반환합니다. (끝까지 탐색에 성공한 경우)
req를 prev1 + prev2로 계산하고, num을 req를 문자열로 변환한 값으로 설정합니다.
x를 빈 문자열로 초기화합니다.
i를 index부터 s의 끝까지 반복합니다.
- x에 s[i]를 한 글자씩 추가합니다.
- x가 num과 같고, ok(s, i + 1, prev2, x를 정수로 변환한 값)의 결과가 true라면 true를 반환합니다.
모든 경우를 확인했는데도 실패하면 false를 반환합니다.

메인 메서드(isAdditiveNumber)에서는 다음 절차를 수행하여 첫 두 숫자의 분할 위치를 결정합니다.

n을 문자열 num의 길이로 설정합니다.
i를 1부터 n - 2까지 반복합니다.
- j를 1부터 i까지 반복합니다.
  - s1은 num의 시작 위치부터 j글자로 이루어진 부분 문자열입니다.
  - s2는 num의 j번째 위치부터 이어지는 부분 문자열입니다.
  - x는 s1과 s2의 길이 중 더 큰 값입니다.
  - x가 n - i보다 크면 남은 글자 수가 부족하므로 다음 반복으로 건너뜁니다.
  - s1 또는 s2가 '0'으로 시작하면서 길이가 1보다 크면 선행 0을 가진 잘못된 숫자이므로 건너뜁니다. ('0' 자체는 유효하지만 '01' 같은 형태는 허용되지 않습니다.)
  - ok(num, i + 1, s1을 정수로 변환, s2를 정수로 변환)의 결과가 true라면 true를 반환합니다.
모든 분할 조합을 시도한 후에도 실패하면 false를 반환합니다.

여기서 long long 타입을 사용하는 이유는 두 수의 합이 int 범위를 넘어 오버플로가 발생하는 것을 방지하기 위해서입니다.

C++ 구현 예제

좀 더 쉽게 이해할 수 있도록 다음 구현 코드를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
    public:
    bool ok(string s, int idx, lli prev1, lli prev2){
        if(idx >= s.size()) return true;
        lli req = prev1 + prev2;
        string num = to_string(req);
        string x = "";
        for(int i = idx; i < s.size(); i++){
            x += s[i];
            if(x == num && ok(s, i + 1, prev2, stol(x))) return true;
        }
        return false;
    }
    bool isAdditiveNumber(string num) {
        int n = num.size();
        for(int i = 1; i < n - 1; i++){
            for(int j = 1; j <= i; j++){
                string s1 = num.substr(0, j);
                string s2 = num.substr(j, i - j + 1);
                int x = max((int)s1.size(), (int)s2.size());
                if(x > n - i) continue;
                if((s1[0] == '0' && s1.size() > 1) || (s2[0] == '0' && s2.size() > 1)) continue;
                if(ok(num, i + 1, stol(s1), stol(s2))) return true;
            }
        }
        return false;
    }
};
main(){
    Solution ob;
    cout << (ob.isAdditiveNumber("112358"));
}

입력

"112358"

출력

출력값 1은 입력 문자열 "112358"이 덧셈 수열을 만족한다는 의미입니다. 즉, 1, 1, 2, 3, 5, 8로 이어지는 피보나치 스타일의 수열이 성립하므로 해당 문자열은 유효한 덧셈 숫자입니다.