[DP_백준 1463번 문제_JAVA] 1로 만들기

내 인생 처음으로 다이나믹 프로그래밍 문제를 풀었다!! 🎆

어제의 나처럼 첫 시작하시는 분들에게 도움이 되길 바라며 글을 써본다

---

 

어제 밤에 문제를 접하고 잠들기 전까지 잊혀지지 않아서

'동적프로그래밍' 으로 유튜브에 검색했을 때 나오는 영상들을

c/java/파이썬 언어불문 전부 재생해서 보면서 잠들었다.

 

그럼에도 불구하고 '재귀함수'라던가 'topdown방식과 bottonup방식'이 뭔지 전혀 이해가 되지 않는 상태였다.

이것 저것 찾아보다가 '사람과 컴퓨터 모두 이해하기 편한 방식' 이라고 쓰여있는 글을 보고 정말 놀라기도 했다... 

 

하지만 누군가가 했으니 나도 할 수 있겠지!! 싶어서

찾아보며 공부한 끝에 문제풀이 성공!

누군가에겐 쉽고 간단한 문제일 수 있으나

시작이 반이라고.. 첫 성공이 감격스러워서 캡쳐까지 했다ㅋㅋ

---

문제풀이는 완벽하진 않지만 제가 이해한 방식으로 풀이 했습니다. 

코드를 보다가 더 좋은 방식이 있다면 피드백 주시면 정말 감사하겠습니다!🙏🏻

---

문제

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

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

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

입력

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

출력

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

 

---

이해한 바로는 일단 동적프로그래밍은 '중복된 코드를 계산하지 않기 위해' 코드를 간편하게 작성하는 것을 목표로 한다.

그렇기 때문에 반복되는 동작이 무엇인지를 발견하는 것이 중요하다.

처음에는 '규칙'을 발견하기 위해 1에서부터 직접 계산을 해보았다. 해보니 아래와 같은 규칙을 찾을 수 있었다.

 

2 -> -1가능, '/2'가능
3 -> -1가능 (연산횟수 : 2만드는방법+1), '/3'가능
4 ->- 1가능 (연산횟수 : 3만드는방법+1), '/2'가능(연산횟수 : 2(4/2) 만드는방법 +1) 
5 -> -1가능 (연산횟수 : 4만드는방법+1) 
6 -> -1가능 (연산횟수 : 5만드는방법+1), '/2'가능(연산횟수 : 3(6/2) 만드는방법 +1 ), '/3'가능(연산횟수 : 2(6/3) 만드는방법 + 1 )
7 -> -1가능 (연산횟수 : 6만드는방법+1) 
8 -> -1가능 (연산횟수 : 7만드는방법+1) + '/2'가능(연산횟수 : 4(8/2) 만든는방법 +1 )  

 

그렇게 발견한 규칙!

n -> (n-1 만든는방법 + 1) or (2의배수이면 n/2방법 +1) or (3의배수이면 n/3방법 +1) 

위에 있는 최대 3가지 방법중에 최소값을 찾으면 된다는 사실!

 

코드로 표현하면 아래와 같다.

 

import java.util.Scanner;

public class Main{
	static int[]d;
	
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		d = new int[num+1];
		System.out.println(cal(num));
		sc.close();
	}
	
	public static int cal(int n) {
		
		//끝나는 지점부터 설정!
		if(n < 2)
			return 0;
		
		//이미 값이 들어있으면 또 계산 할 필요 없이 그냥 그대로 보내!
		if(d[n]>0) {
			return d[n];
		}
		
		//그게 아니면 계산 시작.
		
		//무조건 실행가능한애.
		d[n] = cal(n-1)+1;
	
		//짝수일경우만 실행되는 애.
		if(n%2 == 0) {
			int tmp = cal(n/2)+1;
			if(d[n] > tmp)
				d[n]=tmp;
		}
		
		//3으로 나눠지는경우만 실행되는 애.
		if(n % 3==0){
			int tmp = cal(n/3)+1;
			if(d[n] > tmp)
				d[n]=tmp;
		}
		return d[n];
	}
	
}