[백준] 블랙잭 2798, 분해합 2231

블랙잭 2798

n장의 카드를 뽑아서 m보다 크지 않은 가장 큰 숫자 조합을 만드는 문제였다.
처음에 n장의 카드를 뽑아서 가장 큰 숫자를 만들기만 해도 통과가 됐었는데 생각해보니까 뽑는 카드의 순서가 상관없기 때문에 순열이 아니라 조합으로 문제를 풀어도 상관이 없었다.

나의 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");
const [a, b] = input;
const [n, m] = a.split(" ").map(Number);
const cards = b.split(" ").map(Number);
const visit = Array(n).fill(false);

let answer = Number.MIN_SAFE_INTEGER;
const dfs = (start, sum, count, path) => {
  console.log(path);
  if (sum > m) {
    return;
  }

  if (count === 3) {
    answer = Math.max(sum, answer);
    return;
  }

  for (let i = start; i < visit.length; i++) {
    if (!visit[i]) {
      visit[i] = true;
      dfs(i + 1, sum + cards[i], count + 1, [...path, cards[i]]);
      visit[i] = false;
    }
  }
};
dfs(0, 0, 0, []);
console.log(answer);

분해합 2231

자연수 M과 M의 각 자리의 수를 합한 값이 N일 때 M을 N의 생성자라고 한다더라.
이 문제는 어떤 수가 주어졌을 때 그 수의 가장 작은 생성자를 찾는 문제였다.
0부터 주어진 숫자까지 확인하면 가장 작은 생성자를 찾을 수 있지만, 뭔가 불필요한 계산이 많은거 같다.
나중에 개선할 수 있는 방법이 생각나면 다시 풀어봐야겠다.

나의 풀이

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

const solution = (input) => {
  for (let i = 0; i < Number(input); i++) {
    const sum =
      String(i)
        .split("")
        .map(Number)
        .reduce((a, b) => a + b) + Number(i);

    if (sum === Number(input)) {
      return i;
    }
  }
  return 0;
};

console.log(solution(input));

출처
블랙잭 2798 https://www.acmicpc.net/problem/2798
분해합 2231 https://www.acmicpc.net/problem/2231