[Dynamic Programming] 1436 Java 풀이

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

1463번: 1로 만들기

 

--------------------------------------------------------

풀이 과정

1. 스케치

2. 데모 구현

3. 데모 구현 다듬고 제출

4. 제출 후 논리오류 혹은 에러 캐칭

--------------------------------------------------------

1. 스케치

• 조건문을 3개둔다.
  • 3으로 나누어 떨어지는 지 확인 및 기능수행 (//3)
  • 2로 나누어 떨어지는 지 확인 및 기능수행 (//2)
  • 1을 빼기 (-1)
    • 입력 숫자가 1 ~ 3 일때의 경우의 수를 직접 써본다.
    • 이후의 숫자들은(4 ~ n) 각 계산한 경우의 수로 조합이 가능하다. (DP 조건이 생김)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int x = Integer.parseInt(br.readLine());
        int [] dp = new int[x+3];

        dp[0] = 0;
        dp[1] = 0;
        dp[2] = 1;

        for (int i = 3; i <= x; i++) {

            //dp 배열에는 각 수에 대한 최소 카운트가 들어가 있음
            dp[i] = dp[i-1] + 1;

            //3으로 나누어 떨어질 때 비교 -> 현재 최소 카운트 VS 인덱스를 3으로 나눈 후의 카운트 +1(나눌때의 카운트 증가)
            if (i % 3 == 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);

            //2으로 나누어 떨어질 때 비교 -> 현재 최소 카운트 VS 인덱스를 2로 나눈 후의 카운트 +1(나눌때의 카운트 증가)
            if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            
        }

        System.out.println(dp[x]);
    }
}