백준 - 1436번, 1로 만들기 (sol.java)

◎문제 링크

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

1463번: 1로 만들기

---

◎문제 파악:

할 수 있는 연산

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

 

 

입력된 숫자가 1일 경우: 연산할 필요가 없으므로 0

입력된 숫자가 2일 경우:

1. X가 3으로 나누어 떨어지지 않으므로, 3으로 나누지 않는다.

2. X가 2로 나누어 떨어지므로, 2로 나눈다.

3. 1을 뺀다.

 

1은 실행할 수 없으므로, 최소값은 2로 나눈 경우(연산하면 1이 된다, 최종 연산수: 1)와

1을 뺀 경우(연산하면 1이된다, 최종 연산수: 1)의 최솟값이다.

최솟값 = 1

 

입력된 숫자가 3일 경우:

1. X가 3으로 나누어 떨어지므로, 3으로 나눈다.

2. X가 2로 나누어 떨어지므로, 2로 나눈다.

3. 1을 뺀다.

 

2는 실행할 수 없으므로, 최솟값은 3으로 나눈 경우(연산하면 1이 된다, 최종 연산수: 1)와

1을 뺀 경우(연산하면 2가 된다, 2의 최소 연산 값이 1이므로 최종 연산수 1+1 = 2)의 최솟값이다.

최솟값 = 1

 

입력된 숫자가 4일 경우:

1. X가 3으로 나누어 떨어지지 않으므로, 3으로 나누지 않는다.

2. X가 2로 나누어 떨어지므로, 2로 나눈다.

3. 1을 뺀다.

 

1은 실행할 수 없으므로, 최솟값은 2로 나눈 경우(연산하면 2가 된다, 2의 최소 연산 값이 1이므로 최종 연산수 1+1 = 2)와 1을 뺀 경우(연산하면 3가 된다, 3의 최소 연산값이 1이므로 최종 연산수 1+1 = 2)의 최솟값이다.

최솟값 = 2

 

이런 느낌으로 DP를 사용하여, 2부터 원하는 숫자까지, 1,2,3번 연산 중 가능한 것을 실행하고, 전에 저장된 계산 값을 이용하여 숫자의 최소 연산 값을 구해주면 된다.

---

◎코드 구현

 

 

최초 풀이:

문제점:

나누는 것을 중요히 생각하여, 3으로 또는 2로 나눠질 때까지 빼주는 연산을 시행하였다.

하지만, 이미 이전 배열에 뺸 연산이 적용되어 있으므로  (숫자 4에 관련된 최소 연산 값은 5에서 -1을 한 값의 최소 연산 값이다) 중복하여 계산한 꼴이 되어버렸다.

package ProgrammersBj.MakeItOne;

public class Bj_MakeItOne {
	
	int[] arr; // DP 각 숫자를 1로 만들기 위한 최소 연산 수를 저장한 배열
	
	public void solution(int num) {
		if(num==1) {
			System.out.println(0); 
			return; // 1은 그 자체로 1
		}
		if(num==2 || num==3) {
			System.out.println(1);
			return; // 2/2 = 1, 3/3 = 1
		}
		
		arr = new int[num+1];
		arr[1] = 0;
		arr[2] = 1;
		arr[3] = 1;
		
		/*
		 *  i가 3으로 나눠지면 추가연산 x
		 *  i-1이 3으로 나눠지면 -1을 해줘야하기 때문에 추가연산 = 1
		 *  i-2이 3으로 나눠지면 -2을 해줘야하기 때문에 추가연산 = 2
		 *  
		 *  i가 2로 나눠지면 추가연산 x
		 *  i-1이 2로 나눠지면 -1을 해줘야하기 때문에 추가연산 = 1
		 *  
		 *  i를 3의 배수나 2의 배수로 만들어 2로 나누는것과 3으로 나누는 것중 
		 *  어떤 연산이 가장 작은 연산값을 가지는지 파악
		 *  
		 *  ex. 10 = 2의배수 -> arr[10/2],
		 *       10-1 => 3의 배수 -> arr[9/3] +1
		 *       을 비교하여 작은 값을 저장
		 */
		
		for(int i = 4; i<=num; i++) {
			if(i%3 ==0) { 
				if(i%2==0) { // i가 2로 나눠지면
					arr[i] = Math.min(arr[i/3], arr[i/2]); 
				}else { // i-1이 2로 나눠지면
					arr[i] = Math.min(arr[i/3], arr[(i-1)/2]+1); 
				}
			}else if(i%3 ==1) {
				if(i%2==0) {
					arr[i] = Math.min(arr[(i-1)/3]+1, arr[i/2]);
				}else {
					arr[i] = Math.min(arr[(i-1)/3]+1, arr[(i-1)/2]+1); 
				}
			}else {
				if(i%2==0) {// i-2이 3으로 나눠지면
					arr[i] = Math.min(arr[(i-2)/3]+2, arr[i/2]); 
				}else {
					arr[i] = Math.min(arr[(i-2)/3]+2, arr[(i-1)/2]+1); 
				}
			}
			
			arr[i]++; //2또는 3으로 나눈 연산 횟수 추가
		}
		
		System.out.println(arr[num]);
	}
	
	

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Bj_MakeItOne sol = new Bj_MakeItOne();
		sol.solution(107);
	}

}

 

개선한 풀이:

package ProgrammersBj.Bj_MakeItOne;

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

public class BJ_Improved_solution {

	public void solution(int num) {
		if (num == 1) {
			System.out.println(0);
			return; // 1은 그 자체로 1
		}

		int[] arr = new int[num + 1];
		arr[1] = 0;// 1은 그 자체로 1

		for (int i = 2; i <= num; i++) {
			if (i % 3 == 0) {
				if (i % 2 == 0) {
					// 2로도 3으로도 나눠지는 경우
					// 2로 나눈 값, 3으로 나눈 값, -1한 값 중 최소
					arr[i] = 1 + Math.min(arr[i / 3], Math.min(arr[i / 2], arr[i - 1]));
				} else {
					// 3으로 나눠지는 경우
					// 3으로 나눈 값, -1한 값 중 최소
					arr[i] = 1 + Math.min(arr[i / 3], arr[i - 1]);
				}
			} else {
				if (i % 2 == 0) {
					// 2으로 나눠지는 경우
					// 2으로 나눈 값, -1한 값 중 최소
					arr[i] = 1 + Math.min(arr[i / 2], arr[i - 1]);
				} else {
					arr[i] = 1 + arr[i - 1];
				}
			}
		}

		System.out.println(arr[num]);
	}

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		BJ_Improved_solution sol = new BJ_Improved_solution();
		sol.solution(n);
		
	}

}

---

◎다른 사람의 풀이

package ProgrammersBj.Bj_MakeItOne;

import java.util.Scanner;

public class Bj_Others_Solution {

	@SuppressWarnings("resource")
	public static void main(String[] args) {
		int N = new Scanner(System.in).nextInt(), dp[] = new int[N + 1];

		for (int i = 2; i <= N; ++i)
			/*
			 * 기본적으로 작동 알고리즘은 같지만, 삼항 연산자를 활용하여 획기적으로 짧게 코드를 구현했다.
			 */
			dp[i] = Math.min(dp[i - 1], Math.min(i % 3 == 0 ? dp[i / 3] : N + 1, i % 2 == 0 ? dp[i / 2] : N + 1)) + 1;

		System.out.println(dp[N]);
	}
}

---

◎github codes:

https://github.com/jerry-ryu/java_problemsolving_algorithm/tree/main/%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/Bj_MakeItOne%2C21.05.27

jerry-ryu/java_problemsolving_algorithm