[알고리즘/javascript] 백준 2231번: 분해합

문제 바로가기

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

 

✏️ Problem

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

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

 

🧑‍💻 Solution

 1. N에서 1까지 내려가는 방법

const inptNum = parseInt(require('fs').readFileSync('/dev/stdin').toString().trim());

const resArr = [];
let sum = 0;

for(let i = inptNum - 1; i > 0; i--) {
    sum = i;
    for(let j = 0; j < i.toString().length; j++) {
    	sum += parseInt(i.toString()[j]);
    }
    if(sum === inptNum) resArr.push(i);
}

resArr.length === 0 ? console.log(0) : console.log(resArr[resArr.length - 1]);

입력 받은 숫자부터 1까지 내려가는 방법이다.

생성자가 여러 개가 나올 수 있으니 조건에 맞는 수를 resArr에 담아둔다.

for문이 끝난 후 resArr의 length가 0이 아닐 경우 생성자 중 가장 작은 수인 마지막 인자를 뽑아내야 한다.

 

2. 1에서 N까지 올라가는 방법

const inptNum = require('fs').readFileSync('/dev/stdin').toString().trim();

function findSmallestConstructor(n :number): number {
    for(let i = 1; i < n; i++) {
    	let sum = i;
        let curr = i;
        
        while(curr > 0) {
            // 각 자릿수를 더해준다.
            sum += curr % 10;
            curr = Math.floor(curr / 10);
        }
        
        if(sum === n) return i;
    }
    // 생성자가 없을 경우 0을 리턴
    return 0;
}

console.log(findSmallestConstructor(Number(inptNum)));

1에서 시작해 입력받은 수까지 올라가는 방법이다.

1번 방법에서와는 다르게 각 자릿수를 더하기 위해 나머지 연산과 내림 연산자인 Math.floor를 사용했다.

 

 

알고리즘 초보입니다.. 틀린 부분이나 개선해야 할 부분이 있다면 편하게 댓글 부탁드립니다 🥲