[코딩테스트/백준 알고리즘] 1463번 : 1로 만들기 (Java, 자바 풀이)

문제

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

1463번: 1로 만들기

---

문제 설명

---

문제 풀이

정수 n이 입력으로 들어왔을 때 n에 사용할 수 있는 연산은 아래와 같다.

 

1. n이 3으로 나누어 떨어질 때

memo[n / 3] + 1

 

2. n이 2로 나누어 떨어질 때

memo[n / 2] + 1

 

3. n에서 1을 뺄 때

memo[n - 1] + 1

 

세 값 중 최소값이 memo[n]에 들어가게 된다

---

n이 10일 때, 호출되는 함수

 

n이 10일 때, memo[] 배열

n	1	2	3	4	5	6	7	8	9	10
memo[n]	0	1	1	2	3	2	3	3	2	3

---

코드

import java.util.*;

class Main {
    static int[] memo = new int[1000001];
    
    public static int func(int n) {
    
        if(n == 1) {	//n이 1일 때
            return 0;
        }
        
        if(memo[n] > 0) {	//n에 대한 답이 있는 경우 
            return memo[n];
        }
        
        memo[n] = func(n - 1) + 1;	//1빼기
        
        if(n % 3 == 0) {	//3으로 나누어질 때
            int count = func(n / 3) + 1;
            if(memo[n] > count) {
                memo[n] = count;
            }
        }
        
        if(n % 2 == 0) {	//2로 나누어질 때
            int count = func(n / 2) + 1;
            if(memo[n] > count) {
                memo[n] = count;
            }
        }
        return memo[n];
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(func(sc.nextInt()));
    }
}