[백준] 영화감독 숌 1436, 설탕 배달 2839

영화감독 숌 1436

브루트포스 문제였다. 효율성이 좋지 않더라도 섣부른 최적화는 좋은 결과를 놓칠 수도 있기 마련이다.
이 문제도 뭔가 더 좋은 방법이 있을 것도 같은 느낌이 들지만 브루트포스니까 처음부터 끝까지 모든 수를 확인하는 식으로 문제를 풀었다.

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

const arr = [];

let i = 0;
while (true) {
  if (String(i).includes("666")) {
    arr.push(i);
  }

  if (arr.length === N) {
    break;
  }
  i++;
}
console.log(i);

설탕 배달 2839

3,5 두 수를 최소한으로 사용해서 입력값으로 받은 숫자를 만드는 문제였다.
처음엔 dfs로 문제를 풀려고 했었는데 N이 너무 큰 경우에는 시간초과가 뜨는 것 같다.
그래서 결국 dp로 문제를 해결했는데 dp도 너무 오랜만에 사용해서 그런지 예전에 풀었던 것을 참고해서 풀 수 있었다.

나의 풀이 (DP)

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

const arr = [3, 5];
const dp = Array(N + 1).fill(Infinity);
dp[0] = 0;
for (let i = 0; i < arr.length; i++) {
  for (let j = arr[i]; j <= N; j++) {
    dp[j] = Math.min(dp[j], dp[j - arr[i]] + 1);
  }
}

if (dp[N] === Infinity) {
  console.log(-1);
} else {
  console.log(dp[N]);
}

먼저 3,5를 최소한으로 사용해서 입력값으로 받은 숫자를 만드는 것이 목표기 때문에 dp 테이블을 입력값 숫자+1(0을 추가해주기 위해서)과 큰 숫자(infinity)로 초기화 한다.
dp 테이블에서 인덱스와 값은 숫자(인덱스)를 만들기 위해서 필요한 3 또는 5의 사용횟수(값)를 의미한다.
먼저 dp[0]을 0으로 할당해준다. 왜냐면 어떤 숫자도 사용하지 않을 때 0을 만들 수 있다는 의미이다.
그리고 작은 값부터 시작해서 큰 값으로 이동하면서 이미 만들어진 테이블에 값을 채워나가는 방식이다.
예를 들어 dp[3]이 1인 이유는 0을 만들기 위해 사용한 3,5 사용횟수에서 3을 한번 더하는 경우와 지금까지 만들어진 테이블에서 3과 5를 사용한 사용횟수를 비교해서 작은 값으로 값을 변경해주는 것이다. 이런 식으로 작은 값부터 시작해서 큰 값으로 이동하면서 반복문이 종료되면 숫자를 만들기 위한 최소한의 사용횟수를 테이블이 완성된다.

나의 풀이

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

if (N % 5 === 0) {
  let count = N / 5;
  console.log(count);
} else {
  let f = Math.floor(N / 5);
  let t = 1;
  let num = f * 5 + 3 * t;
  let origin = num;
  while (true) {
    if (f * 5 + 3 * t === N) {
      console.log(f + t);
      break;
    } else if (f * 5 + 3 * t > N) {
      f = f - 1;
      t = t + 1;
      if (f < 0) {
        console.log(-1);
        break;
      }
    } else {
      t = t + 1;
    }
  }
}

먼저 변수 5를 사용한 횟수 f와 3을 사용한 횟수 t를 선언하고 입력값을 5로 나누었을 때 몫으로 f에 할당한다. 5를 최대로 사용했기 때문에 5와 3을 조합해서 만든 값이 입력값 보다 큰 경우에는 5를 사용한 횟수를 줄이고 3을 더 많이 사용하는 방식으로 입력값을 만든다. 만약 5를 사용한 횟수가 0보다 작아진 경우는 3으로도 만들 수 없는 숫자이기 때문에 두 수를 사용해서 만들 수 없는 숫자다. 그래서 -1를 콘솔에 찍어준다.

출처
영화감독 숌 1436 https://www.acmicpc.net/problem/1436
설탕배달 2839 https://www.acmicpc.net/problem/2839