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

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다.

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

---

입력

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

---

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

---

---

문제 접근 방법

이번 문제는 다이나믹 프로그래밍(Dynamic Programming)을 이용하여 쉽게 해결해 줄 수 있는 문제이다.

수를 1로 만드는 방법은 총 3가지가 있다. (-1, /2, /3)

따라서 다이내믹 프로그래밍에 사용할 1차원 배열을 입력으로 들어올 수만큼 선언해준다.(인덱스를 수 그대로 사용할 거면 +1만큼 선언)

따라서 1에서부터 역으로 올라가면서 1로 만드는 3가지의 방법 중 어느 방법이 적은 연산을 하는지 해당 인덱스에 가서 제일 낮은 수를 찾아 +1을 하여 배열에 저장해준다.

ex) 인덱스 3의 배열에 저장할 수 = 

  1. [3-1] + 1

  2. [3/2] X

  3. [3/3] + 1

1, 3번 중에 더 작은 수를 인덱스 3번에 저장해주면 된다. 2번의 경우 2로 나누어지지 않으므로 비교 대상에서 제외된다.

---

JAVA 코드 풀이

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner input = new Scanner(System.in);
	int number = input.nextInt();
	int dp[] = new int[number+1]; // 이전 작업을 저장해 둘 다이나믹 1차원 배열
	for(int i=2; i<=number; i++) {
	dp[i] = dp[i-1] +1; // 1을 빼는 연산이 연산 횟수가 가장 작다고 가정
	if(i%2 == 0) // 현재 숫자가 2로 나누어 떨어지는지 확인
	dp[i] = Math.min(dp[i], dp[i/2]+1); // 현재 저장되어있는 연산 과정과 2로 나누는 연산중 연산 횟수가 더 적은 방법 저장
	if(i%3 == 0) // 현재 숫자가 3으로 나누어 떨어지는지 확인
	dp[i] = Math.min(dp[i], dp[i/3]+1); // 현재 저장되어있는 연산 과정과 3으로 나누는 연산중 연산 횟수가 더 적은 방법 저장
	}
	System.out.println(dp[number]); // 최종 연산 횟수 출력
	}
	}

view raw 1463.java hosted with ❤ by GitHub

코드 실행 결과

---

후기

이 문제를 처음 풀었을 때는 다이나믹 프로그래밍(Dynamic Programming)에 익숙하지 않을 때라 많이 막막하고 어려웠던 문제로 생각했지만, 현재 다이나믹 프로그래밍 문제를 더 풀고 다시 보니 기초에 해당하는 문제였다는 것을 알게 되었다.

---

문제 원본

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

1463번: 1로 만들기