[JAVA] 백준 1463 1로 만들기

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

1463번: 1로 만들기

 

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

    

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

    2. X가 2로 나누어 떨어지면, 2로 나눈다.

    3. 1을 뺀다.

 

- 정수 N이 주어졌을 떄, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 

- 연산을 사용하는 횟수의 최솟값을 출력

 

 

문제 풀이 

 

이걸 어떻게 동적 프로그래밍으로 풀지??

[C++] 백준 1463번 1로 만들기 (tistory.com)

[C++] 백준 1463번 1로 만들기

 

- 동적계획법으로 1을 빼는 경우, 2로 나누는 경우, 3으로 나누는 경우 모든 경우의 수 중 최솟값을 찾아낼 수 있음

- 또한 동적 계획법은 메모이제이션 방법을 사용해 중복되어 계산되는 값을 저장해 효율을 높여줌

 

N을 1로 만들기 위해 필요한 최소 횟수 

= N-1을 1로 만들기 위한 최소 횟수 +1 또는 2나 3으로 나누어지면, 나눠지고 남은 몫의 경우의 연산 +1

 

 

정답

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    static int memo[] = new int[1000001];
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        
        for(int i=2; i<=n;i++)
        {
            memo[i] = memo[i-1]+1;
            
            if(i%2==0)
            {
                memo[i] = Math.min(memo[i], memo[i/2]+1);
            }
            
            if(i%3==0)
            {
                memo[i] = Math.min(memo[i], memo[i/3]+1);
            }
        }
        
        
        bw.write(memo[n]+"");
        bw.flush();
        bw.close();
        
        
        
    }
}