문제 내용은 입력으로 값 두 개를 받아서 왼쪽 값으로 오른쪽 값을 만들어야 하는데 사용 가능한 방법은 2를 곱하는 방법 혹은 우측에 1을 붙이는 방법만 사용할 수 있다(더하는거 아님), 이후 위 방법을 통해 성공했으면 성공 횟수 +1을 출력하고, 실패했을 경우에는 -1을 출력해주면 끝이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int target, ans;
static boolean status;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] split = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
target = split[1];
dfs(Long.valueOf(split[0]), 0);
if (status) {
System.out.println(ans + 1);
} else {
System.out.println(-1);
}
}
public static void dfs(Long current, int count) {
if (current > target) {
return;
} else if (current == target) {
ans = count;
status = true;
return;
}
dfs(current * 2, count + 1);
dfs(Long.valueOf((current.toString() + "1")), count + 1);
}
}경우의 수가 너무나도 많기 때문에 DFS를 사용해줘야 하는데, 어렵게 생각할 필요 없이 현재 값과, 시도 횟수를 넣어 DFS를 호출한 후 현재 값에 * 2, 뒤에 1을 붙이는 방법을 계속 시도해주면 되는데
재귀를 통해 모든 수마다, *2, 뒤에 1 붙이기를 계속 수행해주면서 현재 값이 목표값보다 커졌다면 중단하고, 같은 값이 있을 경우에는 해당 횟수를 넣어주고, boolean을 통해 있다고 처리해준 뒤
DFS가 모두 끝나고 나면 최소 횟수를 찾았을 경우에는 횟수 + 1을 출력해주고 그 외에는 -1을 출력해주면 끝이다.
Leave a Reply