[백준 1463번] 1로 만들기 - JAVA

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

1463번: 1로 만들기

풀이

 

사용한 알고리즘 : DP

 

풀이전략

다이나믹 프로그래밍을 사용해 바텀업 방식으로 풀이하면 되는 문제다.

정수 x에 사용할 수 있는 연산은 3개로,

3으로 나누는 경우, 2로 나누는 경우, 1을 빼는 경우가 있으며 이를 이용해 1을 최종적으로 도출하면 된다.

 

따라서 기본 세팅값으로

d[0]=0, d[1]=0, d[2]=1, d[3]=1 으로 하고 시작한다.

 

d[i] 는 d[i/3]+1, d[i/2]+1, d[i-1]+1 셋 중 가장 작은 값을 가지면 된다.

 

따라서 이를 식으로 나타내면

if(i%2==0 && i%3==0) d[i]=Math.min(Math.min(d[i-1]+1,d[i/3]+1),Math.min(d[i-1]+1,d[i/2]+1));
else if(i%3==0) d[i]=Math.min(d[i-1]+1,d[i/3]+1);
else if(i%2==0) d[i]=Math.min(d[i-1]+1,d[i/2]+1);
else d[i]=d[i-1]+1;

이다.

 

그리고 최종적으로 구해야하는 d[N]의 값을 출력하면 된다.

 

제출코드

import java.io.*;

public class Main {
    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());
        int d[] = new int[1000001];
        d[0]=0;
        d[1]=0;
        d[2]=1;
        d[3]=1;

        for(int i=4;i<N+1;++i){
            if(i%2==0 && i%3==0) {
                d[i]=Math.min(Math.min(d[i-1]+1,d[i/3]+1),
                        Math.min(d[i-1]+1,d[i/2]+1));
            }
            else if(i%3==0) d[i]=Math.min(d[i-1]+1,d[i/3]+1);
            else if(i%2==0) d[i]=Math.min(d[i-1]+1,d[i/2]+1);
            else d[i]=d[i-1]+1;
        }

        bw.write(d[N]+"\n");
        bw.flush();
        bw.close();
    }
}