점화식 세우는데 익숙하지 않아서 조금 헤맨 문제
N 이라는 수가 주어졌을 때 N을 1로 만드는 최소의 방법은
1. N-1 을 1로 만드는 최소 횟수 + 1
2. N/3 을 1로 만드는 최소 횟수 + 1
3. N/2 을 1로 만드는 최수 횟수 +1
중에 최소값 입니다.
즉 d[N] = Min ( d[N-1] , d[N/3] d[N/2] ) + 1 이 됩니다.
Top - Down 방법
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int d[];
public static void main(String args[]) {
Scanner scan = new Scanner(System.in);
int target = scan.nextInt();
d = new int[target+1];
Arrays.fill(d, -1);
d[0] = 0; d[1] = 0;
topdown(target);
System.out.println(d[target]);
}
public static int topdown( int n) {
if(d[n] < 0) {
int min = Integer.MAX_VALUE;
min = Math.min(min, topdown(n-1));
if(n%3 == 0)
min = Math.min(min, topdown(n/3));
if(n%2 == 0)
min = Math.min(min, topdown(n/2));
d[n] = min+1;
return d[n];
}
else {
return d[n];
}
}
}
Bottom - Up 방법
import java.util.Scanner;
public class Main {
static int min;
public static void main(String args[]) {
Scanner scan = new Scanner(System.in);
int target = scan.nextInt();
int d[] = new int[target+1];
d[0] = 0; d[1] = 0;
for(int i = 2; i<=target; i++) {
d[i] = d[i-1]+1;
if(i%3 == 0) {
d[i] = Math.min(d[i/3]+1, d[i]);
}
if(i%2 == 0) {
d[i] = Math.min(d[i/2]+1, d[i]);
}
}
System.out.println(d[target]);
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[BaekJoon] 백준 2193 이친수 -Java (0) | 2020.05.17 |
---|---|
[BaekJoon] 백준 2579. 계단 오르기 - Java (0) | 2020.05.14 |
[BaekJoon] 백준 1932. 정수 삼각형- Java (0) | 2020.05.13 |
[BaekJoon] 백준 11726 2xn 타일링- Java (0) | 2020.05.05 |
[Baekjoon] 백준 9095번 1, 2, 3 더하기- Java (0) | 2020.05.05 |