[java 백준] 실버 3/ 1463번, 1로 만들기

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

1463번: 1로 만들기

Bottom - up 방식

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int n;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        n = Integer.parseInt(st.nextToken());
        int[] dp = new int[n + 1];
 
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
 
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i / 3] + 1, dp[i]);
 
            } else if (i % 2 == 0) {
                dp[i] = Math.min(dp[i / 2] + 1, dp[i]);
 
            }
 
            if ((i % 2 == 0 && i % 3 == 0) && i > 6) {
                dp[i] = Math.min(dp[i / 3] + 1, dp[i / 2] + 1);
            }
        }
 
        System.out.println(dp[n]);
 
    }
 
}

 

우선 내가 택한 방식은 bottom - up 방식이다. 

예를 들어 n이 10일 때,  10/2 ->5-1 ->4/2 ->2/2 해서 4번 안에 1을 만들 수도 있지만

10-1 ->9/3->3/3 으로 3번만에 1을 만들 수 있기에 무조건 나눈다고 최소횟수가 나오는 것은 아니다.

그래서 여기서 변수는 1을 뺐을 때 이므로,

1을 뺐을 때와 3으로 나눴을 때 중 어떤 것이 더 최소값인지 비교해본다.

마찬가지로 1을 뺐을 때와  2로 나눴을 때 중 어떤 것이 최소값인지 비교한다.

그러면 1을 뺀 것, 2또는 3으로 나눈 것 중 최소횟수가 배열에 저장된다. 

---

dp[i / 3] + 1

여기서 1을 더해준 것은 횟수를 한번 더해준 것이다.

 

 

Top - down 방식

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int n;
    public static int[] dp;
 
    public static int cal(int n) {
        if (n == 0 || n == 1) {
            dp[n] = 0;
            return dp[n];
        } else if (dp[n] > 0) {
            return dp[n];
        } else {
            dp[n] = cal(n - 1) + 1;
 
            if (n % 3 == 0) {
                dp[n] = Math.min(cal(n / 3) + 1, dp[n]);
            } else if (n % 2 == 0) {
                dp[n] = Math.min(cal(n / 2) + 1, dp[n]);
            }
            return dp[n];
        }
 
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        n = Integer.parseInt(st.nextToken());
        dp = new int[n + 1];
        System.out.println(cal(n));
    }
 
}

반례를 찾아보고 싶을 때

---

 

https://www.acmicpc.net/board/view/49959