[백준 1463 ] 1로 만들기 java

문제

정수를 문제에서 주어진 연산만을 통해서 1로 만든다.

1로 만들 수 있는 최소 횟수를 출력한다.

가능한 연산 목록

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

풀이 방법

1로 만들 수 있는 최소 횟수를 배열에 저장한다.

arr[i] 는 i를 1로 만드는 최소 횟수이다.

 

기본적으로 arr[i] = arr[i-1]+ 1 로 구할 수 있다.

i 에 -1 연산을 한번 하면 되기 때문이다.

 

따라서 기본적으로 arr[i]=arr[i-1]+1 이다.

여기서 i가 2 혹은 3으로 나누어 떨어지면 arr[i/2]+1 혹은 arr[i/3]+1 로 값을 변경한다.

 

Java 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        if(N==1) {
            System.out.println(0);
            return;
        }else if(N==2||N==3) {
            System.out.println(1);
            return;
        }

        int[] arr = new int[N+1];
        arr[2]=1;
        arr[3]=1;


        for(int i=4;i<=N;i++) {
            arr[i]=arr[i-1]+1;

            if(i%2==0) {
                arr[i]=Integer.min(arr[i], 1+arr[i/2]);
            }
            if(i%3==0) {
                arr[i]=Integer.min(arr[i], 1+arr[i/3]);
            }



        }

        System.out.println(arr[N]);
    }

}