[2231] 분해합(C++)

문제

2231번: 분해합

 

 

해결 방법

진짜 푸는 방법도 간단하고 코드도 간결한 문제인데 너무 터무니없는 곳을 발견하지 못하고 다른 부분을 계속 건드리다가 시간만 많이 날려먹었다...

우선 각 자리수의 합의 최솟값은 1이고 최댓값은 (9 * 자리수)이다. 

즉, 세 자리수인 경우 각 자리수의 합은 최소 1부터 최대 9 * 3 = 27까지이다.

 

그렇다면 우리는 가능한 m의 초기값을 어떤 것에서부터 시작할 것인지를 결정해야 하는데,

1로 초기화 한 뒤에 n과 같아질때까지 계속 돌려도 되고

내가 푼 것처럼  m의 초기값을 (n - 각 자리수의 합의 최댓값) 으로 잡아도 된다.

다만 1로 초기화를 할 경우, n과 같아지는 값을 찾기까지 반복문을 좀 더 많이 돌아야한다.

 

예를 들어보자.

N = 216 이라면 M의 초기값은 (N - 9*3) = 189이고, 

아래와 같이 M을 증가시키면서 각각의 각 자리수의 합이 N과 같아지는 지점을 찾으면 된다.

M	M + 각 자리수 합
189	207
190	200
. . .	. . .
198	216
. . .	. . .

 

내가 실수했던 부분은 처음에 N을 입력받은 뒤 N의 자리수를 구하는 과정이었다.

문자열로 변환하지 않고 자리수를 구하려면 그냥 반복문을 돌리는 수 밖에 없는데, 이게 하기 싫어서 어떻게 간단하게 하지?

생각하다가 자리수를 구하는 코드를

digits = (n / 10) + 1;

 

이렇게 짰다ㅎㅎ

도대체 무슨 생각으로 저렇게 짜고 간단하게 할 수 있네~ 하고 좋아했는지. . .

 

암튼 숫자의 자리수를 알기 위해서는

<string> 헤더에 선언되어있는 to_string 함수를 써서 문자열로 바꾼 뒤,

다시 size() 함수를 사용하여 문자열의 길이를 찾는 방식으로 구하면 된다.

 

그런데 또 주의할 점은, to_string 함수는 C++11 이상부터 적용되기 때문에 

백준에 제출할 때 언어를 C++ 이라고 하면 컴파일 에러가 뜬다.

 

따라서 to_string 함수를 사용했다면 꼭 언어로 C++11 또는 C++17을 선택하여 제출할 것!

 

 

코드(C++)

// [2231] 분해합
// https://www.acmicpc.net/problem/2231
// 브루트 포스

#include <cstdio>
#include <string> // to_string(int), size()
using namespace std;

int sumOfEachDigits(int m, int digits);

int main(void)
{
    int n, m, digits; 
    scanf("%d", &n);
    digits = to_string(n).size(); // n의 자리수
    m = n - 9 * digits; // 각 자리수 합의 최댓값은 각 자리수가 모두 9일 때

    while(m <= n) {
        if(m + sumOfEachDigits(m, digits) == n) {
            printf("%d\n", m);
            return 0;
        }
        m++;
    }
    printf("0\n");
}

int sumOfEachDigits(int m, int digits)
{   
    int sum = 0;
    
    while(digits) {
        sum += m % 10;
        m /= 10;
        digits--;
    }
    return sum;
}