[바미] 분해합

https://www.acmicpc.net/problem/2231

2231번: 분해합

코드 및 코드 설명

const input = require('fs').readFileSync('/dev/stdin').toString().trim();
const N = Number(input);

function findSmallestConstructor(N) {
    // N을 만들 수 있는 최소의 M을 찾기 위해, 1부터 N까지 모든 수에 대해 검사
    for (let M = 1; M < N; M++) {
        let sum = M;
        let temp = M;
        // 각 자릿수를 분해하여 합계에 더함
        while (temp > 0) {
            sum += temp % 10;
            temp = Math.floor(temp / 10);
        }
        // 분해합이 N과 같은 경우, M이 N의 생성자
        if (sum === N) {
            return M;
        }
    }
    // 생성자가 없는 경우 0 반환
    return 0;
}

const result = findSmallestConstructor(N);
console.log(result);

function findSmallestConstructor(N) {...}

findSmallestConstructor함수는 주어진 수 N의 가장 작은 생성자를 찾는 함수입니다.

 

이 함수의 내용을 살펴보면 아래와 같습니다.

for (let M = 1; M < N; M++) {

여기에서  1부터 N-1까지 각 숫자를 생성자 후보로 하여 검사해줍니다.

여기서 M은 생섲아 후보를 나타냅니다.

 

let sum = M;
let temp = M;

 sum을 M으로 초기화하고 temp도 M으로 설정해주는데 여기서 sum은 M과 M의 각 자리수의 합을 계산하기 위해 사용됩니다.

위 변수들은 M의 자릿수를 분해하여 합을 계산하는 데 사용되고 있습니다.

 

while (temp > 0) {
    sum += temp % 10;
    temp = Math.floor(temp / 10);
}

M을 분해하여 각 자리수를 sum에 더해줍니다. 이렇게 되면 % 10은 temp의 마지막 자리수를 얻고, Math.floor(temp / 10)은 temp에서 마지막 자리수를 제거하죠.

 

이 루프는 모든 자리수가 처리될 때까지 계속 동작합니다.

 

if (sum === N) {
    return M;
}

계산된 분해합이 N과 일치하는지 확인하는 부분입니다.

여기서 만약 참이라면, M은 N의 생성자가 되고, 가장 작은 값을 찾기 위해 순차적으로 진행되므로 첫 번째로 발견된 M이 가장 작은 생성자가 됩니다.

 

}
return 0;

그 후 함수가 종료되고, N의 생성자가 없으면 0을 반환합니다.

---

풀이 설명

이 문제도 브루트 포스 방식을 사용한 문제이기 때문에 작은 값을 순차적으로 검사하는 브루트 포스 방식을 사용하여 풀 수 있습니다.

 

문제에서 주어진 자연수 N에 대해, 가장 작은 생성자를 찾기 위해 1부터 N-1까지의 모든 숫자를 생성자 후보로 고려하게 됩니다.

이 범위는 생성자의 정의에 따라 결정되며, 생성자의 분해합은 그 자신보다 클 수 없기 때문에 N보다 큰 숫자는 생성자가 될 수 없죠.

 

그래서 각 후보 숫자(M)에 대하여, 그 숫자와 그 숫자의 각 자릿수의 합을 계산하여 분해합을 구한다 가정했을 때 M = 245인 경우, 분해합은 245 + 2 + 4 + 5 = 256이 됩니다.

 

이랬을 때 계산된 분해합이 N과 일치하는지 검사하여 일치하는 경우, 그 숫자(M)는 N의 생성자가 되는 것이죠.

모든 가능한 M을 검토하고, 처음으로 조건을 만족하는 M을 찾으면, 이후의 검사는 중단하고 해당 M을 결과로 반환하게 되죠.

 

이 알고리즘의 시간 복잡도는 O(N * d)입니다. 여기서 N은 최대 검사 횟수(N-1)이며, d는 숫자 M의 자릿수입니다. 각 숫자 M에 대해 자릿수의 합을 계산하는 데 최대 d번의 연산이 필요하므로, 이 연산이 N번 반복되고, 입력값 N과 몇 개의 지역 변수만 사용하여 추가적인 공간이 필요하지 않기 때문에 공간 복잡도는 O(1)이 됩니다.