문제 내용은 정수 X를 받은 뒤 /3 /2 -1 을 해서 1을 만들 수 있는 가장 빠른 경우의 횟수를 구해줘야 한다, 문제 설명이 간단해서 별 생각없이 풀다가 디테일을 놓치기 쉬운데
1로 만들기만 하면 되는게 아니라, 1을 만들 수 있는 가장 빠른 경우의 수를 찾아야 한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int target = Integer.parseInt(br.readLine());
recv(target, 0);
System.out.println(min);
}
public static void recv(int target, int count) {
if (count > min) {
return;
}
if (target % 3 == 0) {
recv(target / 3, count + 1);
}
if (target % 2 == 0) {
recv(target / 2, count + 1);
}
if (target - 1 > 1) {
recv(target - 1, count + 1);
}
if (target == 1) {
min = Math.min(min, count);
}
}
}문제를 풀어보자면 재귀를 사용해서 풀어줄 수 있는데, 먼저 입력받은 값을 가지고 %3, %2 -1을 해서 0으로 나누어 떨어지거나 1 이상이라면 해당 케이스들을 모두 진행하면서
1이 만들어졌으면 기존 최소값과 비교해서, 신규 최소값을 갈아주면 되고 주의할 점은 경우의 수가 너무 많을 경우 시간 초과에 걸릴 수 있기 때문에 모든 케이스를 진행하면서 최소값 횟수를 넘겨주면 계속 진행할 필요 없이 멈춰주는 것을 잊지 말자
Leave a Reply