백준 1463 / 1로 만들기

문제

풀이

설명

정수 X에 사용할 수 있는 연산은 다음과 같이 세가지이다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다

코드

TopDown

import java.util.Scanner;

public class Num1463 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] d = new int[n+1];
		
		d[1] = 0;
		for (int i=2; i<= n; i++) {
			d[i] = d[i/2] + 1;
			if (i%2 == 0 && d[i] > d[i/2] + 1) {
				d[i] = d[i/2] + 1;
			}
			if (i%3 == 0 && d[i] > d[i/3]+1) {
				d[i] = d[i/3] + 1;
			}
		}
		System.out.println(d[n]);
	}
}

BottomUp

import java.util.*;

public class Main {
    public static void main(String args[]) {
    
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int[] d = new int[n+1];
        d[1] = 0;
        
        for (int i=2; i<=n; i++) {
            d[i] = d[i-1] + 1;
            if (i%2 == 0 && d[i] > d[i/2] + 1) {
                d[i] = d[i/2] + 1;
            }
            if (i%3 == 0 && d[i] > d[i/3] + 1) {
                d[i] = d[i/3] + 1;
            }
        }
        System.out.println(d[n]);
    }
}

코드설명

참고 :
출처 : https://www.acmicpc.net/problem/1463