[1463] 1로 만들기 - Java

 

1. 문제

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

1463번: 1로 만들기

 

2. 풀이

 

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		// 1. Read X
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int X = Integer.parseInt(br.readLine());

		// 2. Calcualte minimum count

		int [] arr = new int[X + 1];
		arr[1] = 0;

		for(int i = 2; i <= X; i++) {

			if (i % 6 == 0){
				
				int compare =  Math.min(arr[i/2], arr[i/3]);
				arr[i] = Math.min(compare, arr[i - 1]) + 1;
			}
			
			else if(i % 3 == 0) {
				arr[i] = Math.min(arr[i/3], arr[i - 1]) + 1;
			}
			
			else if(i % 2 == 0) {
				arr[i] = Math.min(arr[i/2], arr[i - 1]) + 1;
			}
			
			else {
				arr[i] = arr[i - 1] + 1;
			}
		}

		// 3. Print result
		System.out.println(arr[X]);

	}
}

 

3. 배운점

- 3, 2 뿐만 아니라 6으로 나눠지는 경우(둘의 최소 공배수)도 고려해야 한다.

- 큰 수로 나누어 떨어진다고 해서 최솟값이라는 보장이 없다. 따라서 1을 빼주는 경우를 매 조건에서 검토해주어야 한다.

 

4. 개선할 점

 

 

---

풀이 오류 지적, 다른 접근법 공유, 그 밖에 질문 등 모든 의견을 환영합니다.