[백준] 1463 : 1로 만들기 - DP 다시보기

백준 알고리즘 분류 (다이나믹 프로그래밍 (DP)) 

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

# 문제

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

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

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

 

# 예제

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

10

 

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

3

 

# 필요개념

우선 DP에 관한 자세한 내용은 아래 게시글을 참고하면 된다.

https://wanna-developer02.tistory.com/49

[알고리즘] CHAP 2. Dynamic Programming (동적 프로그래밍)

 

이 문제에서는 모든 경우의 수를 고려하여 최소값을 구해야한다.

 

• 6으로 나누어 떨어지는 경우
  • 3으로 나누었을 때
  • 2로 나누었을 때
  • 1을 뺐을 때
• 3으로만 나누어 떨어지는 경우
  • 3으로 나누었을 때
  • 1을 뺐을 때
• 2로만 나누어 떨어지는 경우
  • 2로 나누었을 때
  • 1을 뺐을 때
• 그 외 -> 1을 뺐을 때

위 경우를 고려해 최솟값으로 갱신해준다. 

 

 

# Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Math.*;

public class Main{
    public static int n;
    public static int cnt = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n + 1];

        dp[1] = 0;
        for (int i = 2 ; i <= n ; i++) {
            if (i % 6 == 0) dp[i] = min(dp[i / 2], dp[i / 3]) + 1;
            else if (i % 2 == 0) dp[i] = min(dp[i / 2], dp[i - 1]) + 1;
            else if (i % 3 == 0) dp[i] = min(dp[i / 3], dp[i - 1]) + 1;
            else dp[i] = dp[i - 1] + 1;
        }
        System.out.println(dp[n]);
    }
}

 

# 결과