[백준,BOJ 1463] 1로 만들기(JAVA 구현,추가풀이)

-내 생각

  이번 문제의 경우는 쉽게 풀 수 있었던 것 같다. 처음에는 예제 입력 2의 경우 10이 1이 될 수 있는 경우를 직접 써봤고,  dp배열을 만들어 각 인덱스를 숫자로 하여서 해당 숫자에 도달하기 위한 연산의 수를 저장하고자 했다. 예를 들어 n이 10인 경우 dp [10] = 0부터 시작하여서 10에서 가능한 경우의 수는 -1을 하거나, 2로 나누어 떨어지기 때문에 /2를 하는 경우가 존재한다. 그렇기 때문에 -1을 하게 된다면, dp [10] +1의 값을 dp [9]에 저장하는데 이때 값이 0인 상태라면 그냥 저장하고 0이 아니라면 저장되어 있던 값과 dp [10]+1의 값을 비교해 최솟값을 저장한다. 또 /2의 경우는 dp [5]에 앞선 과정을 반복한다. 이렇게 모든 반복을 1번까지 수행하면 1에는 자연스럽게 최솟값이 저장되는 것이다.

 

-해법

  처음에는 위에 언급했듯이 N부터 1까지 증가시켜 나가면서 경우의 수를 따졌었는데 코드를 작성할 때는 1부터 시작해 N까지 반복하는 것으로 작성하였다. 코드를 보면 쉽게 이해가 될 것이다.

 

import java.util.*;

public class Main {
	static int n;	
	static int dp[];

	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		n=sc.nextInt();
		dp = new int [n+1]; // 1번 인덱스부터 사용하기 때문에 +1
	
		dp[1]=0; // 1부터 시작하므로 0으로 시작
		
		
		for(int i=1;i<=n;i++) { // 1부터 N까지 반복한다.
			if(i+1<=n) // 현재 숫자+1의 값이 N을 넘어가지 않을 경우
				if(dp[i+1] == 0) { // 최초 값 저장인 경우
					dp[i+1] =dp[i]+1; // 그냥 저장
				}else // 이미 값이 존재한다면
				dp[i+1] = Math.min(dp[i]+1,dp[i+1]); // +1한값과 기존 값 중 최솟값 저장 
			if(i*3<=n) // 현재 숫자*3의 값이 N을 넘어가지 않을 경우
				if(dp[i*3] == 0) { // 최초의 값 저장인 경우
					dp[i*3] =dp[i]+1; // 그냥 저장
				}else // 이미 값이 존재한다면
				dp[i*3] = Math.min(dp[i]+1,dp[i*3]); //+1한 값과 기존 값 중 최솟값 저장
			if(i*2<=n) // 위와 동일
				if(dp[i*2] == 0) {
					dp[i*2] =dp[i]+1;
				}else
				dp[i*2] = Math.min(dp[i]+1,dp[i*2]); 
		}
		System.out.println(dp[n]);
		
	}
	
}

 

---

  이전의 풀이보다 좀 더 간단해진 풀이를 올린다. Bottom-up 방식으로 반복문을 사용할 때, 1부터 출발하여 n까지 올라간다고 생각한다.

 

  1. 정수 2가 될 수 있는 경우의 수 - 이전 값+1, 2는 2%2 == 0이므로 2/2 * 2 두 가지가 존재.

  2. 정수 3이 될 수 있는 경우의 수 - 이전 값+1, 3은 3%3 == 0이므로 3/3 * 3 두 가지가 존재.

 

  즉, 모든 경우의 수에는 이전 값 +1이 가능하기 때문에 초기화시킨 후, 2의 배수 또는 3의 배수 여부에 따라 초기화된 값과 비교하여 최솟값을 취하면 된다.

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();
		int dp[] = new int[n+1];
		
		// 2부터
		for(int i=2;i<=n;i++) {
			// 이전 값+1은 모든 경우의 수에 해당하므로 초기화.
			dp[i] = dp[i-1] + 1;			
			if(i % 2 == 0)				
				dp[i] = Math.min(dp[i], dp[i/2]+1);
			if(i % 3 == 0)
				dp[i] = Math.min(dp[i], dp[i/3]+1);
		}
		
		System.out.println(dp[n]);
		
		in.close();
	}

}