[BOJ, JavaScript] 백준 1463번: 1로 만들기 🖤

📌 출처

1463번: 1로 만들기 (acmicpc.net)

📌 문제

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

📌 입력

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

📌 출력

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

📌 예제 입출력

📌 코드

  const fs = require('fs');
  const input = fs.readFileSync("/dev/stdin").toString();

  const N = Number(input);

  const DP = new Array(N+1).fill(0);

  for (let i=2; i<=N; i++) {
    DP[i] = DP[i-1] + 1;

    if (i%2 == 0) { // 2의 배수 (6의 배수 포함 X)
      DP[i] = Math.min(DP[i], DP[i/2] + 1);
    }

    if (i%3 == 0) { // 3의 배수 (6의 배수 포함 O)
      DP[i] = Math.min(DP[i], DP[i/3] + 1);	
    }
  }

  console.log(DP[N]); 

📌 풀이

빨간색: 2의 배수
파란색: 3의 배수

📓 개인 기록용 블로그입니다.
오류가 있을 경우 언제든지 댓글 혹은 메일로 말씀해주시면 감사하겠습니다!

BACK TO TOP ↑