[Java] 백준 풀기 1463 - 1로 만들기

자바 백준 1463번

실버 3

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

1463번: 1로 만들기

 

 

 

 

 

문제 보기

분류: 다이나믹 프로그래밍

 

 

 

 

 

문제 풀기

다이나믹 프로그램으로 저장할 N + 1 개 배열을 생성한다.

2 부터 N 까지 순차적으로 각 연산이 이루어질때 최소 연산의 횟수를 찾고 지속적으로 저장한다.

이는 1을 빼는 연산의 횟수를 저장하고, 만약 i 가 2 또는 3 으로 나누어 떨어지게 되면 그 횟수를 찾아 dp[i] 와 비교하여 최소값으로 다시 저장한다.

N 까지 모든 경우를 확인했을 때 dp[N] 에 저장된 최소 연산 횟수를 반환하여 출력한다.

 

 

 

 

 

코드 보기

import java.util.Scanner;

public class Main {
    
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();  // 입력값

        int result = findMinNumToMakeItOne(N);  // 최소 횟수 찾기

        System.out.print(result);  // 최솟값 출력
    }
    
    public static int findMinNumToMakeItOne (int N) {
        int[] dp = new int[N + 1];  // N까지 연산 횟수를 저장할 dp 배열 생성

        // 1부터 N까지 연산을 수행하여 최솟값을 구함
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + 1;  // 1을 빼는 연산을 수행한 경우

            if (i % 2 == 0)
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);  // 2로 나누는 연산을 수행한 경우

            if (i % 3 == 0)
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);  // 3으로 나누는 연산을 수행한 경우
        }
        
        return dp[N];  // N까지 최소 횟수 반환
    }
    
}