[JS] 백준 1463 - 1로 만들기

문제 링크 - 1로 만들기

문제

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

• X가 3으로 나누어 떨어지면, 3으로 나눈다.
• X가 2로 나누어 떨어지면, 2로 나눈다.
• 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

풀이

세 가지 연산을 사용하여 X를 1로 만드는 최소 연산 횟수를 구하는 프로그램을 작성하는 문제입니다.

문제 해결 전략 (DP 접근)

다이나믹 프로그래밍(DP)은 큰 문제를 작은 하위 문제로 나누어 해결하고, 그 결과를 저장해 재사용하는 방식입니다. 이 문제도 DP를 사용하여 효율적으로 해결할 수 있습니다.

1. 작은 하위 문제로 나누기
이 문제는 숫자 X에서 1로 가는 경로를 찾는 문제입니다. 각 숫자를 1로 만들기 위해 할 수 있는 연산들을 나열하면, 더 작은 숫자에서부터 그 해를 이용해 더 큰 숫자들의 결과를 쉽게 얻을 수 있습니다. 즉, 숫자 X에서 가능한 연산을 통해 바로 다음 숫자로 가는 경로를 작은 하위 문제로 생각할 수 있습니다.


2. 상태 정의
이 문제에서의 상태는 정수 i를 1로 만드는 데 필요한 최소 연산 횟수입니다. 이를 DP 배열에 저장할 수 있습니다.

• dp[i]: 숫자 i를 1로 만드는 데 필요한 최소 연산 횟수
  
  

3. 점화식 설정
숫자 i에서 1로 가는 방법은 세 가지입니다. 각 방법을 적용했을 때의 연산 횟수는 다음과 같이 정의할 수 있습니다:

• 3으로 나눌 수 있으면 dp[i] = dp[i / 3] + 1
• 2로 나눌 수 있으면 dp[i] = dp[i / 2] + 1
• 1을 뺄 수 있으면 dp[i] = dp[i - 1] + 1

이 중 가장 적은 연산 횟수를 선택하면 됩니다.

4. 기저 조건 설정
기저 조건은 숫자 1에 도달했을 때입니다. 숫자 1은 이미 1이므로 더 이상의 연산이 필요하지 않으며, 따라서 dp[1] = 0이 됩니다.

코드

이제 DP 배열을 채우는 방식으로 문제를 해결하는 코드를 작성해보겠습니다.

function makeOne(n) {
  const dp = Array(n + 1).fill(0); // n + 1 크기의 배열을 0으로 초기화

  for (let i = 2; i <= n; i++) {
    // 1을 뺀 경우
    dp[i] = dp[i - 1] + 1;

    // 2로 나누어떨어지는 경우
    if (i % 2 === 0) {
      dp[i] = Math.min(dp[i], dp[i / 2] + 1);
    }

    // 3으로 나누어떨어지는 경우
    if (i % 3 === 0) {
      dp[i] = Math.min(dp[i], dp[i / 3] + 1);
    }
  }

  return dp[n]; // n을 1로 만드는 최소 연산 횟수 반환
}

const n = 10; // 예시 입력
console.log(makeOne(n)); // 10을 1로 만드는 최소 연산 횟수 출력

코드 설명

• 기저 조건 dp[1] = 0이므로 추가 연산이 필요 없습니다. 따라서 for문은 2부터 시작합니다.
• 각 숫자 i에 대해, 1을 빼는 경우, 2로 나누는 경우, 3으로 나누는 경우 중에서 Math.min() 함수를 사용해 가장 적은 연산 횟수를 선택하고, 이를 dp[i]에 저장해 최소 연산 횟수를 구합니다.

이 알고리즘을 사용하면, 숫자 X에서 1로 가는 최소 연산 횟수를 효율적으로 구할 수 있습니다.