백준 : 1로 만들기(1463) with 자바

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

1463번: 1로 만들기

이문제는 간단한 문제이다

2로 나누어지면 2로 나누고, 3으로 나누어지면 3으로 나눈다.

2, 3으로 나누어지지 않으면 1을 빼준다.

위 과정을 반복해서 최소 연산의 수를 구하면 되는 문제이다.

 

바로 코드를 살펴보자

import java.util.Scanner;

public class 일로만들기 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] dp = new int[N + 1];

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

스캐너 객체를 생성한 뒤 N값을 입력받는다.

dp[]를 생성합니다.

for(int i=2; i < N + 1; i++){

i=2부터 i < N + 1까지 반복하는데 2부터 시작하는 이유는 1은 이미 1로 만들어진 상태이기 때문에 2부터 시작합니다.

dp[i] = Math.min(dp[i], dp[i / 2] + 1);

2로 나누어 떨어지면 dp[i], dp[i/2] + 1의 최솟값을 구해서 dp[i] 에 저장하고

dp[i] = Math.min(dp[i], dp[i / 3] + 1);

3로 나누어 떨어지면 dp[i], dp[i/3] + 1의 최솟값을 구해서 dp[i] 에 저장하면 됩니다.

위과정을 거친뒤 dp[N]을 출력하면 최소 연산횟수를 구할 수 있습니다.