[BOJ 1463번] 1로 만들기(JAVA)

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

1463번: 1로 만들기

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	
	public static void main(String args[]) throws Exception {
		int n=Integer.parseInt(br.readLine());
		int[] num=new int[n+1];
		num[0]=0;
		num[1]=0;
		for(int i=2;i<=n;i++) {
			num[i]=num[i-1]+1;
			if(i%2==0) num[i]=Math.min(num[i], num[i/2]+1);
			if(i%3==0) num[i]=Math.min(num[i], num[i/3]+1);
		}
		System.out.println(num[n]);
	}
}

 이 문제는 궁극적으로 연산의 횟수를 카운트하는 문제입니다.

그렇기 때문에 n번째 연산은 n-1번째 연산+1이라는 접근으로 문제를 풀 수 있습니다.

저는 num이라는 정수 배열에 숫자들을 저장했는데요,

for문에서 1, 2, 3번 연산을 했을 때 가장 최솟값을 출력하는 n-1번째 연산을 선택해 n번째 연산은 n-1번째 연산+1으로 하는 식으로 문제를 풀어보았습니다.