홀수 홀릭 호석 (백준 20164)

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

🚀문제 접근

• 수의 각 자리 숫자 중에서 홀수의 개수를 종이에 적는다.
• 수가 한 자리이면 더 이상 아무것도 하지 못하고 종료한다.
• 수가 두 자리이면 2개로 나눠서 합을 구하여 새로운 수로 생각한다.
• 수가 세 자리 이상이면 임의의 위치에서 끊어서 3개의 수로 분할하고, 3개를 더한 값을 새로운 수로 생각한다.

이 단계에 맞춰서 그대로 구현하기만 하면 된다.

다만 까다로웠던 부분은 맨 마지막 부분이다. 임의의 위치에서 끊어 3개의 수로 분할해야하는데 처음에는 재귀를 활용한 조합으로 해결하려고 했다. 하지만 임의의 위치 2곳만 선택하면 되기 때문에 이중 for문을 활용해서 해결할 수 있다.

 

그리고 재귀함수에 cnt라는 파라미터를 넘겨서 총 홀수의 갯수를 구할 수 있도록 구현했다.

 

🛠코드

let input = require('fs').readFileSync(0).toString().trim();

function solution(input) {
   let max = Number.MIN_SAFE_INTEGER;
   let min = Number.MAX_SAFE_INTEGER;

   function count(num) {
      let result = 0;
      for (let x of num) {
         if (Number(x) % 2 !== 0) result++;
      }
      return result;
   }

   function solve(n, cnt) {
      cnt += count(n);
      if (n.length === 1) {
         min = Math.min(min, cnt);
         max = Math.max(max, cnt);
         return;
      } else if (n.length === 2) {
         let temp = Number(n[0]) + Number(n[1]);
         solve(temp.toString(), cnt);
      } else {
         for (let i = 1; i < n.length; i++) {
            for (let j = i + 1; j < n.length; j++) {
               let tmp = Number(n.substring(0, i)) + Number(n.substring(i, j)) + Number(n.substring(j));
               solve(tmp.toString(), cnt);
            }
         }
      }
   }

   solve(input, 0);

   return `${min} ${max}`;
}

console.log(solution(input));