1로 만들기

1로 만들기문제 보기

Silver3

백준📅 2025-07-17

DP메모이제이션

문제 설명

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

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

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

제한사항

1 ≤ N ≤ 106

입출력 예

입력

출력

설명

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

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

입력

출력

설명

10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.

풀이 접근법

시간복잡도 : O(n)

공간복잡도 : O(n)

사용 알고리즘 :

DP메모이제이션

핵심 포인트 :

큰 수부터 작은 수로 분해하면서 최소 연산 횟수 계산
메모이제이션

경계값/반례 :

모든 수는 최소한 1을 빼는 연산으로 1에 도달 가능
N=1일 때 0 반환

핵심 아이디어

각 수에서 가능한 3가지 연산 중 최소 횟수 선택

해결 방법

재귀 + 메모이제이션으로 Top-down DP 구현
각 수에서 가능한 연산(÷3, ÷2, -1) 중 최소 횟수 + 1 반환

핵심 패턴

1️⃣ 비선형 DP

// 선형 DP
static int fibonacci(int n) {
    if (n <= 1) return n;
    if (dp[n] != -1) return dp[n];
    
    return dp[n] = fibonacci(n-1) + fibonacci(n-2);
}


// 비선형 DP
static int dp(int num) {
    if (num == 1) return 0;
    if (dp[num] != -1) return dp[num];
    
    int a = 1000000, b = 1000000;
    if (num % 3 == 0) a = dp(num / 3);
    if (num % 2 == 0) b = dp(num / 2);
    int c = dp(num - 1);
    
    return dp[num] = Math.min(Math.min(a, c), b) + 1;
}

선형 DP : dp[i-1], dp[i-2] 같은 순차적
비선형 DP : dp[i/3], dp[i/2] 같은 나눗셈으로 인한 불규칙

최종 제출 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {

  static int[] dp;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    dp = new int[n + 1];
    Arrays.fill(dp, -1);

    System.out.println(dp(n));
    sc.close();
  }

  static int dp(int num) {
    if (num == 1) return 0;
    if (dp[num] != -1) return dp[num];

    int a = 1000000;
    int b = 1000000;
    if (num % 3 == 0) {
      a = dp(num / 3);
    }
    if (num % 2 == 0) {
      b = dp(num / 2);
    }
    int c = dp(num - 1);

    int min = Math.min(Math.min(a, c), b) + 1;

    return dp[num] = min;
  }
}