[알고리즘 연습] 백준 20164 (홀수 홀릭 호석, 자바스크립트)

문제

20164번: 홀수 홀릭 호석

---

풀이

• 재귀를 돌면서 문자열의 길이에 따라 알맞은 동작을 수행한다.
• 문자열의 길이가 3 이상일 경우 3개의 문자열로 분리할 수 있는 모든 경우를 구한다.
• 홀수의 개수를 누적할 때는 계산이 완료된 숫자를 가지고 홀수의 개수를 구하기 때문에 문자열의 길이가 1인 경우 N 자체에 대해 홀수의 개수를 구한다.

소스 코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");

const N = input[0].trim();
let min = Infinity;
let max = 0;

dfs(N, 0);

console.log(min, max);

/*
   1 - 2, 3, 4
   2 - 3, 4
   3 - 4
*/
function dfs(str, cnt) {
  if (str.length >= 3) {
    for (let i = 1; i < str.length; i++) {
      for (let j = i + 1; j < str.length; j++) {
        const a = str.slice(0, i);
        const b = str.slice(i, j);
        const c = str.slice(j);

        const newStr = String(Number(a) + Number(b) + Number(c));
        dfs(newStr, cnt + check(newStr));
      }
    }
  } else if (str.length === 2) {
    const newStr = String(Number(str[0]) + Number(str[1]));
    dfs(newStr, cnt + check(newStr));
  } else if (str.length === 1) {
    min = Math.min(min, cnt + check(N));
    max = Math.max(max, cnt + check(N));
  }
}

function check(str) {
  let count = 0;

  for (const x of str) count += Number(x) % 2;

  return count;
}