Q1463. 1로 만들기

배열을 활용하여, 1부터 N까지의 숫자를 만들수 있는 최소 횟수를 저장하며, 다음 번호 (i+1, i*2, i*3) 배열에 회수를 저장하는 로직입니다. 

array[2] = 1번, array[3] = 1번, array[4] = 2번, array[5] = 3번, array[6] = 2번, array[7] = 3번 등등

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q1463 { static int[] array; public static void main(String[] args) throws Exception { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int value = Integer.valueOf(st.nextToken()); array = new int[value+1]; array[1] = 0; for (int i = 1; i < value; i++) { int nextArray = i+1; if (nextArray <= value) { setValue(nextArray, i); } nextArray = i*2; if (nextArray <= value) { setValue(nextArray, i); nextArray = i*3; if (nextArray <= value) { setValue(nextArray, i); } } } System.out.println(array[value]); } public static void setValue(int nextArray, int i) { int tempValue = array[i]+1; if (array[nextArray] == 0 || (array[nextArray] > tempValue)) { array[nextArray] = tempValue; } } }