정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static int min = Integer.MAX_VALUE;
public static int recur(int num, int count) {
if (num == 1 || count >= min) {
min = count;
return count;
}
if (num % 3 == 0 && num % 2 == 0) {
int a = recur(num / 3, count + 1);
int b = recur(num / 2, count + 1);
int c = recur(num - 1, count + 1);
return Math.min(a, Math.random(b, c));
} else if (num % 3 == 0) {
int a = recur(num / 3, count + 1);
int b = recur(num - 1, count + 1);
return Math.min(a, b);
} else if (num % 2 == 0) {
int a = recur(num / 2, count + 1);
int b = recur(num - 1, count + 1);
return Math.min(a, b);
} else {
return recur(min - 1, count + 1);
}
}
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.valueOf(br.readLine());
System.out.println();
}
}
그래서 생각했던 것은 각 조건에서 사용할 수 있는 방법들을 Recursive한 값을 구했다. (a, b, c..) 그리고 최소값을 저장할 수 있는 class static 변수를 만들어서 값을 저장하고 값을 초과하면 어김없이 return을 하는 방법이다. 다행히 테스트 케이스를 통과했지만 생각보다 시간이 걸린 것 같았다.
내 코드 시간 : 190ms, 제일 빠른 코드 : 120ms
다른 사람의 코드를 참고해보니 매우 간단해보여서 어떻게 구했는지 분석해보았다.
public static int recur(int num, int count) {
if (num < 2) {
return count;
} else {
return Math.min(
recur(num / 2, count + 1 + (num % 2)),
recur(num / 3, count + 1 + (num % 3)));
}
}
처음이 이 코드를 보고 의문이 들었던 부분은 3방법인 num - 1은 언제하지?의 의문이었다. 그리고 recursive하는 count parameter에는 count + 1 + (num % 2)
가 들어가 있는데 이게 멀까 싶었다.
몇번 살펴보니 내 코드를 굉장히 잘 압축시킨 풀이법이었다. recur에 들어가는 num / 2, num / 3은 기존의 3가지 방법 중 2가지를 적용하였다. 그리고 count + 1 + (num % 2(3))은 혹여나 나누어떨어지지 않는 수였다면 어차피 -1하고 count도 증가하기 때문에 일일히 -1 recursive를 적용할 필요없이 바로 count를 증가시키는 방법이다. 이러한 방법으로 반복적으로 수행해야할 코드들이 많이 줄어들어 결국 시간도 최소화할 수 있었다.