[1463번] 1로 만들기 JAVA☕

www.acmicpc.net/problem/1463

1463번: 1로 만들기

알고리즘 [접근 방법]

이 문제는 크게 3가지 조건이 필요하다.

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

이 조건을 토대로 1로 만들기 위한 최소 연산 횟수를 찾아내야 한다.

여기서 주의할 점은 무조건 "큰수로 나눠서는 안된다"

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];
}

 

[알고리즘 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)));
 
}

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

 

예를들어 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, 2) )
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

 

---

풀이 및 코드

- 방법 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 : [Scanner + 알고리즘 2]

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)));
 
	}
}