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

www.acmicpc.net/problem/1463

 

1463번: 1로 만들기

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

www.acmicpc.net

 

---

• 문제

 

 

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

생각보다 어렵지 않게 풀 수 있는 문제다. 이번 문제는 재귀로 풀이해볼 것이다. 크게 세 가지 경우의 수로 나눌 수 있는데, 3으로 나누는 경우, 2로 나누는 경우, 1을 빼는 경우가 있다. 여기서 1로 만들기 위한 최소 연산 횟수를 찾아내야 한다.

 

여기서 함정이 하나 있다.

"무조건 큰 수로 나눈다고 해결되진 않는다."

 

위 이미지의 힌트에서 볼 수 있듯이 10을 큰 수부터 나눠보기 시작하면 10 -> 5 -> 4 -> 2 -> 1 이렇게 4번의 연산이 필요하다. 하지만 정답은 10 -> 9 -> 3 -> 1 로 3이 정답이다.

 

또한 2와 3의 배수, 즉 6으로 나눠지는 경우의 수도 있다. 그럼 코드로 짠다면 다음과 같은 경우의 수로 나눌 수 있겠다.

 

Integer[] dp; // 메모이제이션 할 배열
static int recur(int N) {
 
	// 탐색하지 않았던 N일 경우
	if (dp[N] == null) {
		// 6으로 나눠질 경우
		if (N % 6 == 0) {
			
		}
		// 3으로만 나눠지는 경우
		else if (N % 3 == 0) {
			
		}
		// 2로만 나눠지는 경우
		else if (N % 2 == 0) {
			
		}
		// 2와 3으로 나누어지지 않는 경우
		else {
			
		}
	}
	return dp[N];
}

 

 

그리고 각 부분에 재귀호출을 하면서 DP를 최솟값으로 갱신해주어야 한다. 이 때 앞서 말한 것 처럼 무조건 큰 수로 나누는 것이 최솟값이 아니기 때문에 이를 조심해야 한다.

 

즉, 6으로 나눠지는 경우는 3으로 나누는 경우와 2로 나누는 경우, 1을 빼는 경우 모두 재귀호출 하여 3가지 경우 중 최솟값으로 DP를 갱신해야 하고, 3으로만 나눠지는 경우는 3으로 나누는 경우와 1을 빼는 경우를 재귀호출, 2로만 나눠지는 경우는 2로 나누는 경우와 1을 빼는 경우의 수를 재귀호출, 그 외에는 1을 빼는 경우만 재귀호출을 해주면 된다.

 

그리고 각 부분에 이전 재귀호출 중 최솟값에 1을 더한 값이 현재 N에 대한 최소연산 횟수가 된다.

말로하면 어려울 테니 알고리즘 부분만 떼어서 코드를 작성하면 다음과 같다.

 

[알고리즘1]

Integer[] dp; // 메모이제이션 할 배열
 
static int recur(int N) {
 
	if (dp[N] == null) {
		// 6으로 나눠지는 경우 
		if (N % 6 == 0) {
			dp[N] = Math.min(recur(N - 1), Math.min(recur(N / 3), recur(N / 2))) + 1;
		}
		// 3으로만 나눠지는 경우 
		else if (N % 3 == 0) {
			dp[N] = Math.min(recur(N / 3), recur(N - 1)) + 1;
		}
		// 2로만 나눠지는 경우 
		else if (N % 2 == 0) {
			dp[N] = Math.min(recur(N / 2), recur(N - 1)) + 1;
		}
		// 2와 3으로 나누어지지 않는 경우
		else {
			dp[N] = recur(N - 1) + 1;
		}
	}
	return dp[N];
}

 

 

이렇게 짜면 알고리즘이 완성된다.

 

 

 

물론 dp를 사용하지 않는 방법도 있다. 아예 재귀 호출 할 때 같이 연산 횟수를 같이 갱신시키는 것이다. 그렇게 해서 N=1 이 되기 전 까지 count를 누적했다가 1이 되면 누적된 count를 반환하여 재귀를 탈출시키는 것이다.

 

코드로 예로들어 보자면 이렇다.

 

[알고리즘 2]

static int recur(int N, int count) {
	if (N < 2) {
		return count;
	}
    
	/*
	 N으로 각각 2와 3으로 나누면 count는 +1에 각 연산의
	 나머지 값을 더해준 것이 된다.
	 나머지 값은 빼기 1했을 때의 count 값과 같기 때문
	*/
	return Math.min(recur(N / 2, count + 1 + (N % 2)), recur(N / 3, count + 1 + (N % 3)));
 
}

 

예로들어 N이 5라고 할 때, 5 -> 4 -> 2 -> 1 로 총 3이 된다.

위 수식의 원리로 보자면 이렇다. recur(N/2, count + 1 + (N % 2)) 를 보자면 이렇게 된다.

N = 5, count = 0

N = 5 / 2 = 2, count = 0 + 1 + 1(나머지값)

N = 2 / 2 = 1, count = 2 + 1 + 0(나머지 값)

N = 1 이므로 return count -> 3이 반환

이런식으로 되는 것이다.

 

물론 그 옆의 recur(recur(N / 3, count + 1 + (N % 3)) 도 있으니 정확하게 말하자면 이렇게 된다.

 

recur(5,0)

min( recur(2,2) , recur(1, 3) )

min( min( recur(1, 3) , recur(0,5) ) , min( recur(0, 3), recur(0, 5) ) )

min( min( 3 , 5 ) , min( 3, 5 ) )

min( 3, 3 )

output : 3

 

 

이런식으로 해줄 수도 있다. 아마 DP를 따로 갱신하지 않고 count만 누적해주면서 나눗셈과 나머지만 필요로 하므로 실제로는 알고리즘2 코드가 좀 더 효율이 좋을 것이다. 그럼 두 가지 경우를 모두 짜주었으니 본격적으로 코드를 보도록 하자.

 

 

 

 

 

 

 

 

 

---

• 4가지 방법을 사용하여 풀이한다.

 

위 알고리즘 설명에서 보여드렸던 두 가지 방식을 토대로 각 알고리즘별 입력방법을 바꾸어 성능을 비교해보고자 한다.

 

1 . Scanner + 알고리즘 1

2. BufferedReader + 알고리즘 1

3 . Scanner + 알고리즘 2

4. BufferedReader + 알고리즘 2

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner + 알고리즘 1]

 

import java.util.Scanner;
public class Main {
 
	static Integer[] dp;
 
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
 
		int N = in.nextInt();
 
		dp = new Integer[N + 1];
		dp[0] = dp[1] = 0;
 
		System.out.print(recur(N));
 
	}
 
	static int recur(int N) {
 
		if (dp[N] == null) {
			// 6으로 나눠지는 경우 
			if (N % 6 == 0) {
				dp[N] = Math.min(recur(N - 1), Math.min(recur(N / 3), recur(N / 2))) + 1;
			}
			// 3으로만 나눠지는 경우 
			else if (N % 3 == 0) {
				dp[N] = Math.min(recur(N / 3), recur(N - 1)) + 1;
			}
			// 2로만 나눠지는 경우 
			else if (N % 2 == 0) {
				dp[N] = Math.min(recur(N / 2), recur(N - 1)) + 1;
			}
			// 2와 3으로 나누어지지 않는 경우
			else {
				dp[N] = recur(N - 1) + 1;
			}
		}
		return dp[N];
	}
 
}

 

 

가장 기본적인 방법이라 할 수 있겠다. 아마 틀린이유야 다양하겠지만, 재귀로 풀 때 위와같은 경우의 수를 안나눠서 틀렸던 분들도 분명 많을 것 같다.

 

 

---

- 방법 2 : [BufferedReader + 알고리즘 1]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
 
	static Integer[] dp;
 
	public static void main(String[] args) throws IOException {
 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		int N = Integer.parseInt(br.readLine());
 
		dp = new Integer[N + 1];
		dp[0] = dp[1] = 0;
 
		System.out.print(recur(N));
 
	}
 
	static int recur(int N) {
 
		if (dp[N] == null) {
			// 6으로 나눠지는 경우 
			if (N % 6 == 0) {
				dp[N] = Math.min(recur(N - 1), Math.min(recur(N / 3), recur(N / 2))) + 1;
			}
			// 3으로만 나눠지는 경우 
			else if (N % 3 == 0) {
				dp[N] = Math.min(recur(N / 3), recur(N - 1)) + 1;
			}
			// 2로만 나눠지는 경우 
			else if (N % 2 == 0) {
				dp[N] = Math.min(recur(N / 2), recur(N - 1)) + 1;
			}
			// 2와 3으로 나누어지지 않는 경우
			else {
				dp[N] = recur(N - 1) + 1;
			}
		}
		return dp[N];
	}
 
}

 

 

 

 

 

 

---

- 방법 3 : [Scanner + 알고리즘 2]

 

 

 

알고리즘 1의 경우 DP를 갱신해주면서 이모이제이션을 했다. 그렇다보니 N-1 즉, 1을 뺀 값도 재귀호출을 해줬어야 했지만, 알고리즘 2 방법은 그럴 필요 없이 나머지 값을 이용하여 count를 갱신해주는 방법이기 때문에 좀 더 효율이 좋을 것이다.

 

 

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
 
		int N = in.nextInt();
		System.out.println(recur(N, 0));
	}
 
	static int recur(int N, int count) {
		// N이 2 미만인 경우 누적된 count값을 반환
		if (N < 2) {
			return count;
		}
		return Math.min(recur(N / 2, count + 1 + (N % 2)), recur(N / 3, count + 1 + (N % 3)));
 
	}
}

 

 

 

아마 수식을 본다면 크게 어렵지 않게 이해했을 것이다. 오히려 코드가 매우 간결해진 것 같다.

 

 

 

---

- 방법 4 : [BufferedReader + 알고리즘 2]

 

 

 

입력방법만 바뀌었을 뿐 별다른 변경점은 없다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
 
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		int N = Integer.parseInt(br.readLine());
		System.out.println(recur(N, 0));
	}
 
	static int recur(int N, int count) {
		// N이 2 미만인 경우 누적된 count값을 반환
		if (N < 2) {
			return count;
		}
		return Math.min(recur(N / 2, count + 1 + (N % 2)), recur(N / 3, count + 1 + (N % 3)));
 
	}
}

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 22116348  -  방법 4 : BufferedReader + 알고리즘 2

채점 번호 : 22116341  -  방법 3 : Scanner + 알고리즘 2

채점 번호 : 22116330  -  방법 2 : BufferedReader + 알고리즘 1

채점 번호 : 22116325  -  방법 1 : Scanner + 알고리즘 1

 

 

위 결과에서 볼 수 있듯 알고리즘에 따라 메모리와 시간차이가 많이 난다. 또한 입력의 경우 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

 

 

 

---

• 정리

 

 

오늘은 간단하게 문제를 풀어낼 수 있었다. 다른 몇몇의 재귀로 풀이하시는 분을 봤는데, 초기에 아예 처음부터 모든 곳을 방문하여 값을 저장한 뒤 이후 3과 2로 나누어 최솟값을 찾는 분들도 있었다. 하지만 그러면 3000ms대를 찍을 정도로 비효율적이기 때문에 추천하는 방법은 아니다.

 

그러니 일단 스스로 고민을 해본 뒤 모르는 부분에서 검색을 해보시거나 하면 좋을 것 같다.

혹여 모르는 부분이 있다면 댓글 달아주시는대로 빠르게 답변드리도록 하겠다.