1로 만들기 ( 백준 1463 )

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

 

* dp 알고리즘을 활용하는 문제

* 순차적으로 증가하는 수열이 아니라서 어떻게 풀어야할지 고민함

* dp[] 배열을 사용할때 3가지 연산이 존재함

* %2, %3을 해서 나누어 떨어질때 하는 연산들은 2의배수 3의배수 일때만 가능함

* -1하는 연산은 어떤 값이든 간에 가능하기 때문에 제일 먼저 연산 시작

* dp[i]-1 = dp[i-1] 해서 1되는지 보지만 dp[i] 값을 보기위해 이항해서 dp[i] = dp[i-1] + 1 식을 활용한다

* dp[i] = dp[i-1] + 1과 2로 나누어 떨어지면 dp[i/2], 3으로 나누어 떨어지면 dp[i/3] 비교해 최소값으로 갱신

* 최종 input 배열에 있는 값을 출력

 

 

* 아이패드에 끄적여 보았다.

* dp[] 배열이 순차적으로 증가하다가 %2와 %3으로 나누어지지 않을때. EX) 5, 7 일때 +1 한값이 최소값

* 나머지는 /2 와 /3 에서 +1 값이 min 값.

 

import java.io.*;
// 1로 만들기 문제
public class BOJ1463 {
    static int input;
    static int[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        input = Integer.parseInt(br.readLine());
        dp = new int[input+1];
        dp[1] = 0;
        for(int i = 2; i <= input; 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.print(dp[input]);
    }
}

 

* 3번째 연산인 -1 값과 dp[i/2]+1 , dp[i/3]+1 값 중에서 제일 작은 값으로 dp[i]로 갱신한다