[백준][JAVA알고리즘]1463번 풀이(1로 만들기) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 1463번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 1463 (1로 만들기)

문제

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

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

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

출력

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

제한

시간제한 : 1 초 (추가 시간 없음)

입력 예시

2

출력 예시

1

입력 예시

10

출력 예시

3

힌트

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

제한

0.15 초

실패 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	static int N ;
	static int[] one = new int[1000001];
	static int min = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		mod(N);
		System.out.println(min);
}
	public static void mod(int count) {
		
		if(count==1) {
			min = Math.min(min, one[N]);
			return;
		}

			if(count%3==0) {
				one[N] += 1;
				mod(count/3);
				one[N] -= 1;
			}
			
			if(count%2==0) {
				one[N] += 1;
				mod(count/2);
				one[N] -= 1;
			}
			
			one[N] += 1;
			mod(count-1);
			one[N] -= 1;
		
	}
}

해당 코드는 정답은 나오지만 시간 초과가 나온다. 그 이유는 간단하다. 바로 메모 이제이 션 기법을 사용하지 않았기 때문이다. 이에 따라 코드를 살 짝만 바꿔주면 바로 성공 코드가 된다.

 

성공 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	static int N ;
	static Integer[] one;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		one = new Integer[N+1];
		one[0] = one[1] = 0;
		
		System.out.println(mod(N));
		
}
	public static int mod(int count) {
		
		if(one[count] == null) {
		if(count%6==0)
			one[count] = Math.min(mod(count/3), Math.min(mod(count/2), mod(count-1))) + 1;
		else if(count%3==0) 
			one[count] = Math.min(mod(count/3), mod(count-1)) + 1;
		else if(count%2==0) 
			one[count] = Math.min(mod(count/2), mod(count-1)) + 1;
		else
			one[count] = mod(count - 1) + 1;
		}
		
		return one[count];
	}
}

1로 만들기 알고리즘에서 중요한 점은 바로 IF문 걸러야 할 숫자들을 자 파악해야 하는 것입니다. 저도 이것 때문에 많이 헛고생하다 결국 다른 분껄 참고하고 깨닫게 되었죠...

 

기본적인 메모이제이션이 무엇인지는 이전 글들을 참고하시면 됩니다.

 

그럼 간단히 STEP을 따라가 보면서 이해를 도와드리겠습니다.

---

알고리즘 흐름도

입력받기 -> 조건 만족해 주기 -> 출력하기

---

STEP1 조건 이해하기

 사실 이번 문제에서의 핵심은 바로 조건을 이해하고 해당 조건을 만족하는 최적이 조건을 IF문으로 구현하면 되는 문제입니다.

 

조건을 살펴보면

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

 

조건만 보면 굉장히 간단하지만, 여기서 힌트를 보시면, 10 9 3 1로 3번으로 되는 것을 알 수 있습니다.

이 말은 즉, 다시 생각해보면, 2로 나누어질 수 있더라도 -1을 먼저 하면 더 최적의 방법으로 1에 도달할 수 있음을 알려줍니다.

 

자 만약에 10이라면, 우선적으로 조건에서 말하는 3으로는 나누어지지가 않습니다. 그렇다면 2로 나눈 갚고 -1을 한 값 중에서 더 빠르게 1로 도달하는 방법을 알아내면 된다는 의미가 됩니다.

 

여기서 우리가 편히 구할 수 있는 방법은 바로 최소 값을 알아내는 것입니다.

 

우선은 해당 문제를 풀기 위한 변수를 먼저 선언해 주어야 합니다.

		N = Integer.parseInt(br.readLine());
		one = new Integer[N+1];
		one[0] = one[1] = 0;

일단 입력을 받고 해당 입력보다 1이 큰 INTEGER배열을 선언해 줍니다. (반듯이 INTEGER로 해야 합니다.)

 

(여기서 INTEGER와 INT는 객체와 변수의 차이입니다. 쉽게 설명하자면 INTEGER은 NULL값을 가질 수 있고 INT는 안된다고 아시면 됩니다.)

 

왜 1을 크게 해 주냐. 이거는 저희가 인데스가 바로 그 숫자라고 인식하기 위해서입니다.

 

그래서 0번과 1번 인덱스에는 0을 넣어줍니다. 왜냐하면 0의 경우 필요 없는 수이고, 1의 경우 그 자체로 이미 답은 만족하기에 1로 다가가는 수가 0이기 때문이죠

 

다음 STEP으로 넘어가며 조건에 대한 완전한 이해와 구현까지 도와드리겠습니다.

---

STEP2 조건 구현하기

 

 STEP1에서 어느 정도 조건을 이해하셨다면, 해당 식까지는 쉽게 세우실 수 있습니다. 여기서 살짝의 이해를 돕기 위해서 one이라는 배열은 숫자가 1에 도달하기 위한 최소한의 방법의 수를 의미합니다.

 

public static int mod(int count) {
		
		if(one[count] == null) {
		if(count%3==0) 
			one[count] = Math.min(mod(count/3), mod(count-1)) + 1;
		else if(count%2==0) 
			one[count] = Math.min(mod(count/2), mod(count-1)) + 1;
		else
			one[count] = mod(count - 1) + 1;
		}
		
		return one[count];
	}

첫 번째 if에서 null을 해준 것은 기본적으로 integer를 선언한다면 null값이 들어있죠. 즉 해당 인덱스의 값이 null이란 소리는 재귀를 실행하지 않은 배열의 인덱스라는 뜻. 그렇다면, 저희는 해당 인덱스 값을 구할 필요가 있습니다.

(바로 메모이제이션의 핵심이죠) 만약 해당 if문에 걸리지 않다면, 이미 값이 있다는 의미이므로 해당 값은 그냥 반환해주면 끝!

 

안에 있는 if, else if, else문은 앞서 STEP1에서 알려드렸던 최솟값을 비교해주는 방법입니다. 뒤에 +1은 경우의 수를 하나씩 늘려주는 역할을 하죠 3으로 나누어지면 -1과 비교해서 더 낮은 값을 넣어주죠. 이해가 되지 않으시면 예시로 설명드리겠습니다.

------------------------------------------------------------------------------- 예시

10이 들어온다면

one [11] 0 0 n n n n n n n n n

이런 식으로 선언이 되어있겠죠 (여기서 n은 null을 의미)

자 이제 mod(10)이 실행됩니다.

 

당연히 null이 아니니 해당 값에 들어갑니다. 가장 처음 걸리는 것은 바로 else if문 그렇다면 비교합니다이제.

mod(5)와 mod(9) 값 중의 최소 값을 찾으러 갑니다.

 

물론 둘 다 null 값임으로 다시 한번 재귀를 해줍니다.

 

 - mod(5)

mod(5)의 경우 else에 걸리게 되겠죠. 그렇다면 mod(4)가 실행되죠

mod(4)의 경우 else if에 걸립니다, mod(2), mod(3)의 최솟값을 찾으러 갑니다.

 

mod(2)의 경우 else if에 걸립니다. mod(1)과 mod(1)이 됩니다. 여기서 mod(1)은 null이 아니기에 0을 반환합니다.

그렇다면 뒤에 + 1이 되기 때문에 mod(2) = 1이 됩니다.

 

mod(3)의 경우 if에 거리게 됩니다. mod(1)과 mod(2)에 걸리게 됩니다. 여기서 최소는 mod(1) 즉, 0이 반환됩니다.

mod(3)의 경우도 mod(3) = 1이 됩니다.

 

그렇다면 mod(4)의 경우 최솟값인 1이 반환이 되면서 mod(4) = 2가 됩니다. 결론적으로 mod(5)는 3의 값을 가지게 됩니다.

 

이런 식으로 mod(9)의 값을 도출해 내면 2의 값을 가지게 됩니다. 2, 3중에 최솟값은 2

 

그렇다면 결론적으로 mod(10)은 2 + 1 즉, 저희가 원하는 3의 값을 갖게 됩니다.

-----------------------------------------------------------------------

 

그런데 여기서 제가 계속 틀린 이유가 있습니다. 바로 2와 3이 동시에 가능할 때를 고려해 주지 않았습니다. 즉 6으로 나누어질 때를 고려해줘야 합니다.

	public static int mod(int count) {
		
		if(one[count] == null) {
		if(count%6==0)
			one[count] = Math.min(mod(count/3), Math.min(mod(count/2), mod(count-1))) + 1;
		else if(count%3==0) 
			one[count] = Math.min(mod(count/3), mod(count-1)) + 1;
		else if(count%2==0) 
			one[count] = Math.min(mod(count/2), mod(count-1)) + 1;
		else
			one[count] = mod(count - 1) + 1;
		}
		
		return one[count];
	}

이런 식으로 6으로 나누어질 때는 3 나누기, 2 나누기 1뺴기를 모두 비교해주어야 한다는 것입니다...... 해당 조건을 정확히 이해하셨다면, 바로 생각할 수 있었지만, 저는... ㅜㅜ

 

사실 조건을 정확히 이해만 하셨다면, 쉽게 풀이하실 수 있었던 문제였습니다.