문제
문제풀이
예를 들어 정수 X가 10일 때, 1로 만들기 위해서는
10 -> 5 -> 4 -> 2 -> 1 방법으로 4번 연산을 통해 값을 구할 수 있지만,
10 -> 9 -> 3 -> 1 과 같이 3번의 연산을 통해서 1을 만들 수 있다.
코드
이를 메모이제이션을 사용하는 동적 계획법을 이용해서 함수를 만들어서 Bottom-up 방식을 통해서 큰문제를 작은문제로 나누어서 작은 문제부터 풀어나가는 방식으로 코드를 작성하였다.
import java.util.Scanner;
public class Main{
//메모이제이션 할 배열을 정적 필드로 선언한다.
static Integer[] dp;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
//새로운 배열 선언
dp = new Integer[num + 1];
dp[0] = dp[1] = 0;
System.out.print(recur(num));
}
static int recur(int N){
//초기화전 dp는 null값을 가진다.
if(dp[N] == null){
//3과 2 둘 다 나눌 수 있는 경우, 세가지 경우 중 최소값을 선택한다.
if(N % 6 == 0){
dp[N] = Math.min(recur(N-1), Math.min(recur(N/3), recur(N/2)))+1;
}
//3으로 나눌 수 있는 경우,
else if(N % 3 == 0){
dp[N] = Math.min(recur(N/3), recur(N-1)) +1;
}
//2로 나눌 수 있는 경우,
else if(N % 2 == 0){
dp[N] = Math.min(recur(N/2), recur(N-1)) +1;
}
//2와 3로 나눌 수 없는 경우,
else{
dp[N] = recur(N-1) +1;
}
}
return dp[N];
}
}알고리즘 공부를 시작하면서 처음으로 풀어본 동적 계획법 문제이다.
처음 개념에 대해 숙지하지 않고 풀고, 다시 개념을 숙지하고 푸는데 시간이 꽤 오래 걸리지만 하나하나 알아가는 맛에 알고리즘 공부가 재밌다...!!
