[BOJ/백준] 2231번: 분해합(C++)

2231번: 분해합 문제 링크

📌문제

분해합 문제를 C++로 풀어보고자 했다. BruteForce로 굉장히 유명한 문제이고 예전에 python으로 풀었었는데 이번에는 c++로 풀어봤다.

✔️Solution

1. 해당 문제는 1,000,000의 수까지 주어지기 때문에 전체 수를 돌더라도 시간초과가 되지 않는다 ! ➡️BurteForce 이구나 라고 생각!
2. 입력에는 분해합이 주어진다. for문을 통해 n보다 작은 전체 수를 돌면서 해당하는 생성자를 찾으면 될 것 같다.
3. i값과 각 자리의 숫자를 더한 값을 구하고 최소 생성자를 구한다.
4. 이때 생성자가 없는 경우는 0으로 출력한다.

⭐주의사항

• 생성자가 여러개일 수 있음 ! -> 가장 작은거 출력해야하므로 전체를 for문을 통해 돌아야함
• n을 string으로 바꾸는 과정과 자리수를 다시 숫자로 바꾸는 작업에서 주의하기

처음 작성한 코드

int desSum(int n){
    int min_sum=1e6;

    int i;
    for(i=n-1; i>0; i--){
        int sum = 0; // 분해합 전체 합
        string n_str = to_string(i); // 숫자 i를 string으로 숫자로 바꿔줌
        int n_size = n_str.size(); // n의 자리수

        sum += i;
        cout<<sum<<endl;
        for(int j=0; j<n_size; j++){
            sum += int(n_str[j]);
        }
        
        if(sum == n){
            min_sum = min(i, min_sum);
        }
    }
    if(min_sum==1e6){
        return 0;
    }

    return min_sum;
}

-> 해당과정에서 0이 return되는 오류가 계속 발견됐다

for(int j=0; j<n_size; j++){
            sum += int(n_str[j]);
            cout<<n_str[j]<<endl;
            cout<<"합"<<sum<<endl;
}     

• 위 과정을 통해 전체 sum과 각자리숫자를 출력해보았다.
  

-> 2,1,5로 각자리 숫자와 합을 출력해보았더니 각자리 char값은 잘 출력됐는데, 합이 이상한 숫자가 출력됐다.

[해결방안]
현재 int(n_str[j])로 char -> int로 변경시키고 있었는데 이러한 경우 2의 아스키코드 값 50이 더해지므로 오류가 발생한 것이다.
sum += n_str[j] - '0'; -> 이렇게 char의 int 값을 구할 수 있다. ('0'의 아스키코드 값을 빼주면 int의 값을 출력가능하다.

최종 코드

int desSum(int n){
    int min_sum=1e6;

    int i;
    for(i=n-1; i>0; i--){
        int sum = 0; // 분해합 전체 합
        string n_str = to_string(i); // 숫자 i를 string으로 숫자로 바꿔줌

        int n_size = n_str.size(); // n의 자리수

        sum += i;
        for(int j=0; j<n_size; j++){
            sum += n_str[j] - '0';
        }

        if(sum == n){
            min_sum = min(i, min_sum);
        }
    }
    if(min_sum==1e6){
        return 0;
    }

    return min_sum;
}

이렇게 가장 작은 생성자를 출력가능하다.