[백준 : 실버3] 1로 만들기(1463 번) : DP(Java)

이번 문제는 동적프로그래밍으로 어떻게 풀어보려고 했으나 아직 익숙치 않은지 감이 잡히질 않았다.

그래서 답을 보게 되었는데 이제 약간 동적프로그래밍이 뭔지 알것 같다.

 

문제부터 살펴보자.

 

문제

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

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

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

입력

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

출력

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

 

 

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

 

 

문제 접근

이번 문제는 동적 프로그래밍으로 정수 N까지에서 생길수 있는 모든 최소값들을 구하고 

거기서 값을 구해내는것이다.

 

그래서 N까지의 생길수 있는 모든 최소값을 구하기 위해서는 일단 재귀호출이 이루어져야 하고

 

그 재귀호출은 아래와 같은 조건에서 호출이 되어져야 한다.

 

3으로 나눠 떨어졌을때 3으로 나누는게 적은지 아니면 -1 한 값으로 한게 더 적인지

2로 나눠 떨어졌을때 2로 나누는게 적은지 아니면 -1 한값이 적은지

 

이 두개의 조건에서 호출이 되어져야 하는데

 

여기서 하나더 추가해야할것은 

2와 3의 공통 배수인 6이다.

 

6같은 경우는 정수 N이 6으로 나눠 떨어졌을때 2로 나누는게 더 적은지 3으로 나누는게 더 적은지 

더 적은 값을 선택하는것이다.

 

그렇게 소스는 아래와 같아진다.

 

	public int giveMin1(int num,Integer[] dp) {
		
		if(dp[num] == null) { //dp[num]이 비어 있다면 진입
			
			if(num%6 == 0) { //6으로 나누어 떨어지는 경우는 3으로 나누는 경우와 2로 나누는경우중 작은것을 택하게 한다.
				dp[num] = Math.min(giveMin1((num/2),dp), giveMin1((num/3),dp))+1;
			}else if(num%3 == 0) {//3으로 나눈것과 -1한것중 작은것을 택한다.
				dp[num] = Math.min(giveMin1((num/3),dp), giveMin1((num-1),dp))+1;
			}else if(num%2 == 0) {//2로 나눈것과 -1한것중 작은것을 택한다.
				dp[num] = Math.min(giveMin1((num/2),dp), giveMin1((num-1),dp))+1;
			}else {//-1한 값을 넣는다.
				dp[num] = giveMin1((num-1),dp)+1;
			}
		}
		
		return dp[num];
	}

 

 

이렇게 되면 재귀적으로 호출을 하면서 제일 하단의 값을 특정 배열에 넣고 이미 값이 있다면 해당 값을 가져다 쓰는것이다.

 

이 방식이 동적 프로그래밍의 가장 기본적인 규칙인대 이것에 대한 자세한 설명은 아래 링크에 나와 있으니 확인해보면 될것 같다.

https://wpioneer.tistory.com/120

[자료구조] 동적계획법 알고리즘 ( Dynamic Algorithm)

 

 

이처럼 특정 배열을 사용해서 할수도 있지만 아래와 같은소스로 그저 count를 리턴해서 값을 사용하는 방법도 있다고 한다.

	public int giveMin2(int num,int count) {
		if(num<2) { //2보다 작으면 count return
			return count;
		}
		
		return Math.min(giveMin2((num/2),count+1+(num%2)),giveMin2((num/3),count+1+(num%3)));
	}

 

이렇게 하면 소스도 간결해지고 메모리도 덜 차지하게 된다.

 

그리고 수행시간을 좀더 줄이고 싶다면 Scanner 대신 BufferedReader를 쓰면 된다.

https://wpioneer.tistory.com/156?category=1023662 

BufferedReader와 BufferedWriter

 

무튼 근데 개인적으로 나는 동적 프로그래밍을 좀더 이해해주는 방법은 첫번째 방법인것 같다.

 

 

 

느낀점

1. 동적프로그래밍은 값을 저장하는것이 중점인대 값을 저장하기 위해선 재귀호출을 통해서 제일 밑에단까지 가서 저장해야 한다.

2. 수행시간을 좀더 줄이기 위해선 Scanner보단 BufferedReader를 사용하자.

 

 

 

참고 사이트

https://st-lab.tistory.com/133

[백준] 1463번 : 1로 만들기 - JAVA [자바]