[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 코드 풀이

코드 실행 결과

---

후기

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

---

문제 원본

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

1463번: 1로 만들기