[백준] 2231. 분해합 (브루트포스 알고리즘/완전탐색/자바스크립트/node.js/javascript/알고리즘/코딩테스트)

[백준] 2231. 분해합

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	192 MB	46347	22149	17735	47.722%

 

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

 

예제 입력 1

216

 

예제 출력 1

198

 

---

내가 작성한 코드 (자바스크립트)

let fs = require('fs');
let input = fs.readFileSync("/dev/stdin").toString();
const N = Number(input);
let start = N - (String(N).length * 9);
let M = start;
let answer;
while(true){
    M++;
    let sum = M;
    for(let i = 0; i < String(M).length; i++){
        sum = sum + Number(String(M).charAt(i));
    }
    if(sum === N){
        answer = M;
        break;
    }
    if(M >= N){
        answer = 0;
        break;
    }
}
console.log(answer);

브루트포스 알고리즘(=완전탐색) 유형은 가능한 모든 경우를 다 대입하여 풀 수 있는 알고리즘으로 말 그대로 무식하게 힘으로 푸는 알고리즘이다.

입력이 최대 백만(1,000,000)이지만 O(n)의 시간복잡도로 문제를 풀 수 있기 때문에 가능한 경우의 수를 전수조사해도 문제는 풀린다.

그러나 최대한 메모리와 시간을 단축시켜보고자 시작값과 종료값의 범위를 대폭 줄였더니 시간이 120ms로 확 줄었다.

 

문제를 설명해보자면, 어떤 자연수 M을 가지고 M + (M의 각 자리수의 합)을 하면 N이 나오는데, 이 때 M을 N의 생성자 라고 한다. N이 주어졌을 때 이 N의 생성자를 구하는 문제이다.

그냥 M을 1부터 시작해도 되겠지만, 시작값을 정해주는 것만으로도 반복문 횟수를 많이 줄일 수 있으므로 시작값을 설정해준다.

시작값은 N은 M + (M의 각 자리수의 합) 으로 구성이 되기 때문에 N이 만약 세자리라면 M + (a + b + c) = N라고 할 수가 있고, 각 자리수의 최대값은 9이므로 M + ( 9+9+9) = N이라고 봐도 무방하다. 그래서 시작값은 N에서 N의 자리수 * 9를 빼주면 된다.

예를 들면 216의 경우 M + 9 + 9 + 9 = 216이 최대값이고 216 - (3 * 9) = 189가 시작값이 된다. 189보다 작은 수들은 볼 필요도 없다는 것이다.

이렇게 시작값을 정해준 후 M을 1씩 증가하며 조건에 부합한다면 반복문을 탈출하면 된다.

또한 종료값은, 그리고 M이 N과 같아지는 순간, M에서 절대 N이 나올 수 없으므로 반복문을 탈출하면 된다.