[알고리즘 떠먹여 주는 남자] 백준 2231 - 분해합 for Node.js

안녕하세요!

오늘의 알고리즘은 백준 온라인 저지의 브루트포스 카테고리 2번째 문제 분해합입니다. 저는 알고리즘 문제를 해석할 때 항상 애를 먹는데요, 왜 그런지 모르겠습니다. 몇 번을 읽어도 헷갈리고.. 그래서 실수를 자주 하고는 하는데요, 어떻게 개선해 나가야 할 지 아직 감이 잘 잡히지 않습니다.. 일단은 무식하게 노력해 보는 수 밖에 없겠네요, 마치 브루트포스처럼.

 

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

2231번: 분해합

문제

어떤 자연수 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

 

문제 풀이

문제를 읽어보면 주어진 입력값 N (분해합) 의 최소 생성자값을 구하라고 합니다. 분해합의 생성자는 2가지 조건을 가질 수 있는데요:

• 한 개, 혹은 여러 개 일 수 있다. 이 경우에 최소 생성자값을 출력해야 한다.
• 분해합의 생성자가 존재하지 않을 수도 있다. 이 경우에 0을 출력해야 한다.

입니다. 분해합을 구하는 공식은 문제에 이미 주어졌으니 바로 제가 작성한 코드로 넘어가도록 하겠습니다.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : `${__dirname}/input.txt`;
const input = fs.readFileSync(filePath).toString().trim();

const disassembledSum = Number(input);
let minConstructor = disassembledSum;

for (let i = disassembledSum; i >= 1; i--) {
  const assembledIndexDigitsSum = String(i).split('').reduce((previousValue, currentValue) => {
    return parseInt(previousValue) + parseInt(currentValue);
  }, 0);

  if (i + assembledIndexDigitsSum > disassembledSum) continue;
  if (i + assembledIndexDigitsSum === disassembledSum && i < minConstructor) minConstructor = i;
}

console.log(minConstructor !== disassembledSum ? minConstructor : 0);

코드 길이는 생각보다 길지 않지만, 저는 문제를 어떻게 풀어야 하나 고민하는 데에 시간을 꽤 많이 (약 3~40분) 소비했습니다. 정말 알고리즘은 풀어도 풀어도 어렵네요.. 이렇게 알고리즘만 푼다고 해결 될 문제는 아닌 것 같고 문제 접근방식을 찾는 능력을 길러야 할 것 같다는 생각이 듭니다.

 

제가 선언하고 사용한 변수 목록은 아래와 같습니다.

disassembledSum - 분해합

minConstructor - 최소 생성자

assembledIndexDigitsSum - for loop 인덱스 각 숫자의 합

 

제 문제 풀이 접근 방식은, 반복문 하나를 사용하여 i 가 주어진 입력값부터 역순으로 확인 하였습니다. 먼저 현재 인덱스의 각 숫자의 합을 구해주고, 만약 그 숫자들의 합과 현재 인덱스의 합이 주어진 입력값을 넘어갈 경우 continue 를 사용하여 다음 인덱스로 넘어가게끔 했습니다. 분해합의 컨셉에 위반 되기 때문입니다.

 

만약 현재 인덱스의 각 숫자의 합에 인덱스 값을 더해 준 합이 입력값과 동일하고, 현재 인덱스 값이 최소 생성자 값보다 작을 경우 최소 생성자 값에 현재 인덱스 값을 대입해 줌으로서 최소 생성자 값을 업데이트 해주었습니다.

 

마지막 console.log 출력문에 만약 현재 최소 생성자 값이 입력값 (분해합) 과 동일할 경우 위에 제시 된 두 번째 조건에 의하여 0을 출력해 주고, 그렇지 않을 경우 최소 생성자 값을 출력해 주게 하였습니다. 그럼 결과는!

 

제출 결과

다행히 한방에 통과했습니다. 제 알고리즘 풀이 제출 히스토리를 보면 빨간 글씨로 떡칠이 되어 있는 게 많은데, 이번 문제는 한 번에 통과해서 기분이 매우 좋읍니다 ^.^

 

오늘 (저에겐) 어려운 알고리즘을 하나 풀었으니 알고리즘은 공부는 그만 하고 다른 부분을 좀 봐야겠습니다. 그럼 모두 열공 하시고 또 뵈어요~