[백준 node.js] boj 1463 풀이

po4tion·2021년 5월 8일
0

백준

목록 보기
9/13

1463 1로 만들기

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. X가 2로 나누어 떨어지면, 2로 나눈다.
  3. 1을 뺀다.
    정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

테스트케이스

  • 입력

2

  • 출력

1

  • 입력

10

  • 출력

3

소스 코드

// 1463번 1로 만들기
const rl = require('readline').createInterface(process.stdin, process.stdout);

let input = 0,
  idx = 0;

rl.on('line', (line) => {
  input = +line;
}).on('close', () => {
  // 입력받은 길이 N 만큼의 배열을 0으로 초기화
  const init = Array.from({ length: input }, () => 0),
    cnt = 1;
  init[0] = 0;

  while (++idx < input) {
    init[idx] = cnt + init[idx - 1];

    // 3과 2로 나눠지는 수들 조심
    // else if 썻다가 틀림
    if ((idx + 1) % 2 === 0) {
      init[idx] = Math.min(init[idx], cnt + init[(idx + 1) / 2 - 1]);
    }

    if ((idx + 1) % 3 === 0) {
      init[idx] = Math.min(init[idx], cnt + init[(idx + 1) / 3 - 1]);
    }
  }

  let answer = init[init.length - 1];

  console.log(answer);
});

메모리 / 시간

  • 메모리

16656 KB

  • 시간

284 ms

포인트

  • 다이나믹 프로그래밍의 Bottom-up 방식을 사용
  • 1을 먼저 빼고 다른 연산을 하는 방식2나 3으로 나누는 연산 방식 중 최소 값을 갖는 연산 순서를 택해야 한다
  • 2로 나눠지지 않으면 3으로 나눠지게 else if 조건문을 넣었다가 계속 틀렸다. 2와 3의 공배수 중에 2로 먼저 나눴을 때와 3으로 먼저 나눴을 때 최소 값이 달라지는 정수 X(30)가 존재한다.
profile
배움, 학습 그리고 성장.

관심 있을 만한 포스트

0개의 댓글