[백준 - Java] 1463번 : 1로 만들기

문제

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

 

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

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

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

입력

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

출력

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

 

1. 작게 만들면 가장 최소로 연산을 할 수 있을까? (X)

그렇다면 무조건 3으로 나눌 수 있으면 3으로 나누는 것이 가장 최고일 것.

3 나누기 > 2 나누기 > 1 빼기 이러한 우선순위로 연산을 하는 것이다.

 

ex) 10

10 / 3 (X)

10 / 2 (5) 선택!

10 - 1 (9)

 

5 / 3 (X)

5 / 2 (X)

5 - 1 (4) 선택!

 

4 / 3 (X)

4 / 2 (2) 선택!

4 - 1 (3)

2 / 3 (X)

2 / 2 (1) 정답!

2 - 1 (1)

4번이나 걸렸음

 

2. 그럼 1부터 시작해서 N까지 간다면 최소 연산을 할 수 있지 않을까? (X)

ex) 10

1 * 3 (3) 선택!

1 * 2 (2)

1 + 1 (2)

 

3 * 3 (9) 선택!

3 * 2 (6)

3 + 1 (4)

 

9 * 3 (27)

9 * 2 (18)

9 + 1 (10) 정답!

 

하지만 30을 예를 들어보자.

30의 정답은 (30 - 10 - 9 - 3 - 1)의 순서로 4번이 최소 횟수이다.

하지만 2번 방식(1부터 시작해서 N까지 가면서 구하기)으로 구해보면 

 

ex) 30

1 * 3 (3) 선택!

1 * 2 (2)

1 + 1 (2)

 

3 * 3 (9) 선택!

3 * 2 (6)

3 + 1 (4)

 

9 * 3 (27) 선택!

9 * 2 (18)

9 + 1 (10)

 

27 * 3 (81)

27 * 2 (54)

27 + 1 (28) 여기서 29 30 이런 식으로 1 더하기만 하게 됨 -> 그럼 총 6번이 걸림

3. 1번 2번 둘 다 안됨 (X)

다른 방법을 생각해야 함

 

내 머리로는 해결하기 힘들 거 같아서 다른 사람의 풀이도 보고 결국 강의까지 찾아봤다.

이분의 영상 덕에 완벽히 이해할 수 있었다.

 

https://www.youtube.com/watch?v=VOG-FfILfiM

즉, 10의 경우

3으로 나누기는 안되고 2로 나누기, 1로 빼기의 연산을 할 수 있다.

그리고 두 가지의 계산으로 5와 9가 나오게 되는데 이때 나온 수가 또다시 1이 되게끔 할 최소 연산을 해야 하는 것이다.

나올 수 있는 경우에서의 최소 횟수를 모두 구하며 끝까지 비교해봐야 알 수 있는 것

 

이 방법은 딱 느낌이 오지 않는가?

재귀를 사용하는 것! 

왜냐 3을 나누고 2를 나누고 1을 빼고 계속 구해지는 숫자에 대해서 같은 연산을 하기 때문이다.

 

10 / 2 = 5 // (5를 1로 만드는 최소 횟수) + 1번
10 - 1 = 9 // (9를 1로 만드는 최소 횟수) + 1

 

근데 예를 들어 12의 경우,

 

12 / 3 = 4,   4 / 2 = 2
12 / 2 = 6,   6 / 3 = 2

 

이렇게 두 연산을 해서 2라는 똑같은 값이 겹친다.

어차피 같은데 3으로 나누고 2로 나누고 두 번 계산하면 비효율적이다.

 

그래서 전에 계산한 결과를 기억해 놓고 다시 활용해 효율성을 높이는 것이다.

이러한 방식으로 문제를 푸는 방식이 DP = Dynamic Programing = 동적 계획법 방식이다.

4. DP 구현 과정과 점화식

점화식이란?

수학에서 점화식 또는 재귀식이란 수열에서 이웃하는 두 개의 항 사이에 성립하는 관계를 나타낸 관계식이다.

 

https://ko.wikipedia.org/wiki/점화식

재귀 함수를 만들기 위해 점화식을 세우는 과정

 

https://m.blog.naver.com/PostView.nhn?blogId=occidere&logNo=220787315353&proxyReferer=https:%2F%2Fwww.google.com%2F

이 분의 포스팅을 보면 아주 자세하게 재귀 호출의 방법을 알 수 있다.

 

만약 N=2,3이면 당연히 1로 만드는 경우의 수는 1이 된다. 
여기서 이를 수식으로 바꿔보면 d[3을 1로 만드는 최소 횟수] = 1번, d [2를 1로 만드는 최소 횟수] = 1번이 된다.

그렇다면 4의 경우는 어떨까?
d[4를 1로 만드는 최소 횟수] = 
  (1) N-1을 하면 N=3이 되고, 다시 N/3을 하면 1이 된다. => 2번
  (2) N/2를 하면 N=2가 되고, 다시 N/2나 N-1을 하면 1이 된다. => 2번
  (3) N/3의 경우는 불가능하다.
결국 이 경우의 수 중에서 제일 작은 값인 2번이 된다.

즉 N을 최소 횟수로 1로 만드는 과정은

"주어진 수(N)에서 -1 또는 /2 또는 /3을 하여 수를 최소 횟수로 줄여나가 1까지 만든다"의 사고 과정을 따른다.

 

그러나 이를 조금 바꿔 다른 말로 표현해 보자.

주어진 수(N)을 1로 만드는 최소 횟수는 =  'N-1을 1로 만드는 최소 횟수 + 1번' 또는 'N/2를 1로 만드는 최소 횟수 +1번'

또는 'N/3을 1로 만드는 최소 횟수 + 1번' 이 된다. (약간 비약적인 일반화가 있긴 했지만 N에 수를 대입해보면 이해가 갈 것이다.)

이를 식으로 표현하면 d[N을 1로 만드는 최소 횟수] = d[N-1을 1로 만드는 최소 횟수] + 1번

또는 d[N/2를 1로 만드는 최소 횟수] + 1번 or D[N/3을 1로 만드는 최소 횟수] + 1번이 된다.

따라서 이를 일반화시켜 점화식을 만들면 아래와 같다.

 

dp[i] = dp[i - 1] + 1; 
if (i % 2 == 0) dp[i] = MIN(dp[i], dp[i / 2] + 1); 
if (i % 3 == 0) dp[i] = MIN(dp[i], dp[i / 3] + 1);

 

이렇게 식으로 표현해놓고 보면 복잡하다고 생각할 수 있는데 전혀 그렇지 않다.

우선 식의 i가 위의 예시에서 쓰인 4라고 생각해보자.

첫째줄에선 무조건 주어진 수(i)를 1로 만드는 최소 횟수는 = 'i-1을 1로 만드는 최소 횟수 + 1번'으로 한다.

즉, 무조건 -1을 해서 해당 숫자를 만든다는 얘기다. (4를 만드는 최소 횟수 = 3을 1로 만드는 최소 횟수 + 1번)

물론 이게 진짜 최소 횟수로 나올 확률은 낮다.

하지만 이는 /2를 한 경우나 /3을 한 경우와 비교를 하기 위해 먼저 써준 것뿐이며, /2나 /3이 안될 경우에는 이 값이 결국 최소 횟수 값을 계산하는데 쓰이게 된다. (i=5인 경우가 그 예이다.)

이제 둘째 줄로 넘어가면 주어진 수(i)가 2로 나누어짐과 동시에 'i-1을 1로 만드는 최소 횟수 + 1번'보다 

'i/2을 1로 만드는 최소 횟수 + 1번'이 작은 경우, 

주어진 수(i)를 1로 만드는 최소 횟수는 = 'i/2을 1로 만드는 최소 횟수 + 1번'으로 바꿔준다.

쉽게 말해 i=4인 경우에 i-1을 하면 3이고, 3을 1로 만드는 경우의 수는 1이므로 총 2번이 되는데,

4는 2로 나눠지기 때문에 i/2를 하면 2이고, 2를 1로 만드는 경우의 수는 1이므로 총 2번이 된다.

그런데 여기서 두 수는 서로 같기 때문에 값이 변경되지는 않는다.

같은 방식으로 셋째 줄에서 주어진 수(i)가 3으로 나누어짐과 동시에 

'i-1을 1로 만드는 최소 횟수 + 1번'보다 'i/3을 1로 만드는 최소 횟수 + 1번'이 작은 경우, 

주어진 수(i)를 1로 만드는 최소 횟수는 = 'i/3을 1로 만드는 최소 횟수 + 1번'으로 바꿔준다.

여기까지 했으면 최솟값으로 d[i]가 되어있을 것이다.

그런데 여기서 포인트는 더해주는 숫자가 +1이란 것이다.

이는 즉 연산의 횟수를 더해주는 것으로 -1, /2, /3중 무엇을 하던 연산은 1번을 수행했기에 +1을 해주는 것이라고 보면 된다.

i자리에 숫자를 하나씩 넣어보며 생각해 보면 이해가 갈 것이다.
이제 이를 모아서 코드로 구성하면 아래와 같다.

 

* 크게 동적계획법은 두 가지 방식으로 나뉘는데 재귀(Top-Down) 방식, 반복문(Bottom-Up) 방식이 있다.

 

자세히 알고 싶다면 아래 포스팅을 추천한다.

 

st-lab.tistory.com/123

5. Bottom -Up 코드

N값을 입력받고, 이 값에 대해 dp 한 값을 저장할 배열을 만든다.

 

배열의 크기는? N보다 1 큰 값으로 만들어준다.

1부터 N까지의 dp 한 값을 갖기 위해서는 하나 더 인덱스가 늘어나야 N까지의 결과를 저장할 수 있으니까!

 

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
        
		int dp[] = new int[n + 1];
        
		dp[0] = dp[1] = 0;
        
		for (int i = 2; i <= n; i++) { //최종 숫자는 n이기 때문에 n까지 반복연산
			// 3이나 2로 나누어지지 않으면, 주어진 숫자-1에 대한 최소 연산 횟수 + 연산을 한 횟수 1
			dp[i] = dp[i - 1] + 1;
           
			// 3으로 나누어 떨어지는 경우, 연산 횟수 dp값이 더 적다면 갱신 
			if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
			
			// 2로 나누어 떨어지는 경우, 연산 횟수 dp값이 더 적다면 갱신 
			if (i % 3 == 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
		}
        
		System.out.println(dp[n]);
        
		sc.close();
	}

6. Top - Down 코드

배열을 전역 변수로 선언한 이유는 함수 안에서 최대 100만이 되는 사이즈가 큰 배열을 선언하면 스택 사이즈 때문에 에러가 날 수 있다.

왜냐하면 자바 가상 머신의 스택 사이즈가 100만을 아마 효용 할 수 없을 것이다.

그래서 지역변수에 큰 배열을 선언하면 스택이 터져서 오류가 나는 것

전역 변수는 힙 공간에 잡히니까 저런 제한에서 자유롭다.

 

* 21. 03. 25일 한 달 전인가? 문제가 재채점 되어서 기존의 코드가 시간 초과가 나왔다.

 

// 1. 기존 solve 함수 코드에서 3과 2로 나누어 떨어질 경우
if(n % 3 == 0)
	dp[n] = Math.min(dp[n], solve(n/3)+1);
    	
if(n % 2 == 0) 
	dp[n] = Math.min(dp[n], solve(n/2)+1);
  
// 2. 변경된 solve 함수 코드       
if(n % 3 == 0 && dp[n] > solve(n/3)+1)
	dp[n] = dp[n/3] + 1;
    	
if(n % 2 == 0 && dp[n] > solve(n/2)+1) 
	dp[n] = dp[n/2] + 1;

 

위와 같이 solve 함수에서 3과 2로 나누어 떨어지는 부분의 코드에서

현재 n의 dp 값보다 나눈 dp값이 작은 경우만 dp[n] 값을 갱신해주도록 했다.

 

import java.util.Scanner;

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

 

아래와 같은 코드도 가능하다.

 

import java.util.*;

public class Main {
	public static int N, dp[];
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
        
		dp = new int[N+1];
		Arrays.fill(dp, -1);
        
		dp[0] = dp[1] = 0;
        
		System.out.println(solve(N));
        
		sc.close();
	}

	public static int solve(int n){
		if(dp[n] != -1) 
			return dp[n];

		int min = Integer.MAX_VALUE;
        
		if(n % 3 == 0) 
			min = Math.min(min, solve(n / 3));
        
		if(n % 2 == 0) 
			min = Math.min(min, solve(n / 2));
        
		min = Math.min(min, solve(n - 1));

		return dp[n] = min + 1;
	}
}

GITHUB

github.com/KwonMinha/BOJ/tree/master/BOJ%231463/src

KwonMinha/BOJ