1로만들기
-
[알고리즘]다이나믹프로그래밍-1로만들기알고리즘 2022. 2. 21. 22:30
정수 X에 사용할수있는연산은 다음과같이 세가지 1. X가 3으로 나누어 떨어지면 3으로 나눈다. 2. X가 2로 나누어떨어지면 2로나눈다. 3. 1을 뺀다. 예제 ) 8 , 10 최소 : 8 4 2 1 (3회) 3으로 먼저 나누려는 경우 : 8 7 6 2 1 (4회) 최소 : 10 9 3 1 (3회) 2로 먼저나누려는 경우 : 10 5 4 2 1 (4회) 점화식 구하기 2나 3의 배수일 경우 바로 구한다. 아닐경우 -1을 하여 다시 구한다. public static int[] arr; public static int calc(int n){ if( n== 1 ){ return 0; } if( arr[n] > 0 ){ return arr[n]; } arr[n] = calc( n-1 ) + 1; //2로 나누..