[C/C++] Carry 피하기 /백트래킹/ 코드트리

코드트리 Carry 피하기 문제 

https://www.codetree.ai/problems/escaping-carry/description

 

n개의 숫자가 주어지고, 그 숫자를 적절하게 골라 더했을 때 carry가 전혀 발생하지 않는 최대로 고를 수 있는 숫자의 수를 계산하는 프로그램을 작성해보세요.

여기서 carry란, 수와 수를 더했을 때, 10의 자리를 넘기는 것을 말합니다. 예를 들어 3과 6을 더하면 9가 되고 자리수가 넘어가지않아 carry가 발생하지 않지만, 5와 7은 더하면 12가 되므로 carry가 발생합니다. 또, 81과 72를 더하면 일의 자리를 더할때는 carry가 발생하지 않더라도 십의 자리를 더할 때는 carry가 발생하게 되므로 불가능한 조합입니다. 즉, 각 자리수를 모두 각각 더해봤을 때 10 이상이 되는 경우가 전혀 없어야 한다는 뜻입니다.

입력 형식

첫 번째 줄에는 n이 주어집니다.

두 번째 줄부터는 n개의 줄에 걸쳐 숫자가 주어집니다.

• 1 ≤ n ≤ 20
• 1 ≤ 숫자의 범위 ≤ 100,000,000

출력 형식

carry가 발생하지 않는 최대로 고를 수 있는 숫자의 개수를 출력합니다.

 

---

 

Carry 피하기 문제 풀이

이 문제는 carry가 발생하지 않을 때 더할 수 있는 최대 갯수를 구하는 문제이다.

따라서, 모든 경우의 수를 다 따져봐야하는 백트래킹 알고리즘을 사용해야한다. 

 

백트래킹이란?

= 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다. 

 

따라서, 재귀를 어느정도 사용한다고 생각하면 된다. 

 

사실 이런 백트래킹 문제가 많이 익숙치 않아 풀면서 좀 헤맸던 것 같다.

정답코드랑 비교해봤을 때 코드의 간결성이 많이 달랐다..ㅋㅋ 

 

처음에는 Carry 인지 아닌지 판별하는 함수와 만약 Carry가 아닐 때 더하면서 계속 나아가는 시퀀스를 큰 틀로 2개를 짜야했다. 

 

1. Carry 인지 아닌지 판별하는 함수

 for(int i = 0; i< 10; i++){
            if(i == 0){
                num1[0] = a_val%10;
                num2[0] = b_val%10;
                if(a_val < 10 || b_val < 10 ) break;
                a_val = a_val/10;
                b_val = b_val/10;
                continue;
            }

            num1[i] = a_val%10;
            num2[i] = b_val%10;
            if(a_val < 10 || b_val < 10 ) break;
            a_val = a_val/10;
            b_val = b_val/10;
        }
        
        for(int i = 0; i< 10; i++){
            if(num1[i]+num2[i] >= 10){
                flag = 1;
                break;
            }

 

이런식으로 계속해서, a_val이란 변수를 1의 자리를 체크하고 10으로 나눈 몫으로 다시 1의 자리를 구하는 알고리즘을 구현했다.

 

이렇게 구현했는데, 해설 코드는 너무 간단해서 배울께 많았다.

 

bool canAddWithoutCarry(int x, int y) {
    // 각 자리수를 비교하여 carry가 발생하는지 확인합니다.
    while (x > 0 && y > 0) {
        if ((x % 10) + (y % 10) >= 10) return false; // 자리수 합이 10 이상이면 carry 발생
        x /= 10; // 다음 자리수로 이동
        y /= 10; // 다음 자리수로 이동
    }
    return true; // carry가 발생하지 않으면 true 반환
}

 

새삼 간단하지 않은가.. 

큰 조건을 while문 조건으로 쓰고, 결과적으로 구해야되는 조건으로 return을 줌으로써 간결성을 유지했다.

 

나도 반복문을 쓸 때 while문 같은 조건을 주어서 코드의 간결성을 지켜나가야겠다. 

 

2. 더할  수 있는 수의 최대 개수 구하기

나는 이 부분에서 flag를 세워서 flag가 0 일 경우 재귀로 넘어가게끔 코드를 짰다. 

 

해설 코드는 Carry 판별함수가 True면 재귀로 넘어가는 식으로 간단하게 짰다. 

 

// 최대 부분집합을 찾는 함수입니다.
void findMaxSubset(int index, int currentSum, int currentCount) {
    // 현재까지의 최대 개수를 갱신합니다.
    if (currentCount > maxCount) maxCount = currentCount;
    // 더 이상 진행할 필요가 없는 경우 종료합니다.
    if (index >= numCount || currentCount + numCount - index <= maxCount) return;
    
    // 현재 숫자를 포함할 수 있는 경우
    if (canAddWithoutCarry(currentSum, numbers[index])) {
        findMaxSubset(index + 1, currentSum + numbers[index], currentCount + 1);
    }
    // 현재 숫자를 포함하지 않는 경우
    findMaxSubset(index + 1, currentSum, currentCount);
}

 

함수로 들어오면 maxCount인지 확인한 후, return 조건을 확인한 다음 판별하는 순서로 코드 간결성 부분에서 많이 배울 수 있었다. 

 

---

전체 내가 짠 코드 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int result = 0;
vector<long long> vec;
int n;
int check(long long a, long long b, int a_num, int b_num, int ex_val){

    int who_final = 1;
    int flag = 0;
    int remem_a = a;
    int val = ex_val;
    while(1){
        if(flag = 1) {
            a = remem_a;
            flag = 0;         
            who_final = max(who_final, val);
            val = ex_val;
        }
        int a_val = a;
        int b_val = vec[b_num];

        int num1[10] = {0,};
        int num2[10] = {0,};
        
        for(int i = 0; i< 10; i++){
            if(i == 0){
                num1[0] = a_val%10;
                num2[0] = b_val%10;
                if(a_val < 10 || b_val < 10 ) break;
                a_val = a_val/10;
                b_val = b_val/10;
                continue;
            }

            num1[i] = a_val%10;
            num2[i] = b_val%10;
            if(a_val < 10 || b_val < 10 ) break;
            a_val = a_val/10;
            b_val = b_val/10;
        }
        
        for(int i = 0; i< 10; i++){
            if(num1[i]+num2[i] >= 10){
                flag = 1;
                break;
            }
        }
        
        if(flag == 0) {
            val++;
            a = a+vec[b_num];
            
            if(b_num +1 < n) who_final = max(check(a, vec[b_num+1], a_num, b_num+1, val),who_final);
            else who_final = max(who_final, val);
            flag = 1;
        }

        if(b_num +1 < n) b_num++;
        else break;
    }
    return who_final;
}
int main() {
    cin >> n;
    for(int i = 0; i< n; i++){
        long long num;
        cin >> num;
        vec.push_back(num);
    }
    for(int i = 0 ; i< n-1; i++){
        for(int j = i+1; j< n; j++){
           int vaule = 0;
           vaule = check(vec[i],vec[j],i,j, 1);
           result = max(result, vaule);           
        }
    }
    cout << result;
    return 0;
}