[백준] 1463: 1로 만들기

'1463- 1로 만들기' 문제로 이동!

👉문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

👉입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

예시 - 10

👉출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예시 - 3

---

✍내 풀이

⭐ 처음 제출한 풀이

import java.util.*;

public class Main {

	static ArrayList<Integer> list = new ArrayList<Integer>();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		list.add(0);
		
		int n = sc.nextInt();
		System.out.println(makeOne(n));
	}
	
	static int makeOne(int num) {
		if( list.size() > num) {
			return list.get(num);
		}

		if(num %3 ==0) {
			return Math.min(1 + makeOne(num/3), 1+ makeOne(num-1));
		}
		else if(num %2 ==0) {
			return Math.min(1 + makeOne(num/2), 1+ makeOne(num-1));
		}
		else {
			return  makeOne(num-1);
		}

	}
	
	
}

결과 : 시간초과
이유 : min으로 비교할때 밑에 줄줄이 딸린 계산들이 많고 심지어 min으로 계산한 뒤에 더 큰부분은 버려짐,, 시간복잡도 낭비😣

---

⭐ 재제출 풀이

import java.util.*;

public class Main {

	static int[] arr = new int[1000001];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		arr[0] = 0;
		arr[1] = 0;
		int n = sc.nextInt();
		System.out.println(makeOne(n));
	}
	
	static int makeOne(int num) {
		//Bottom Up 방법 
		for( int i = 2 ; i <= num ; i ++) {
			arr[i] = arr[i-1] + 1; // 1을빼는 상황을 계산해서 배열에 넣음
			
			if(i %2 ==0 ) arr[i] = Math.min(arr[i], 1+arr[i/2]);
			if(i %3 ==0 ) arr[i] = Math.min(arr[i], 1+arr[i/3]);
		}

		return arr[num];
	}
}

---

✍Note

Bottom Up 방식의 동적계획법으로 문제를 풀었다.
재귀로 낭비되는 시간복잡도가 많고, 이미 계산한 결과를 또 활용하는 경우가 많아서 메모이제이션을 활용함
DP문제를 처음 풀어서 공간스런 혼란이였읍미다.