1463번 - 1로 만들기
1이 들어갈 수 없는 값들을 입력했을 때도 1이 뜨는데 초보라서 이유를 잘 모르겠네요
알고리즘 고수님들 도와주세요!!
import java.util.ArrayList;import java.util.Scanner;
public class Main { // static ArrayList<Integer> list = new ArrayList<>(); static int count=0; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); makeOne(scanner.nextInt()); list.sort(null); System.out.println(list); } public static void makeOne(int x){ int temp =x; if(x==1){ list.add(count); count=0; return; } if(x%3==0){ count++; makeOne(temp/3); } if(x%2==0){ count++; makeOne(temp/2); } count++; makeOne(temp-1); }}
우선 그 문제보다는 알고리즘 상에 문제가 있어보입니다.
3으로 나눠지면 먼저 3으로 나누고
아니면 2, 아니면 1 이런식으로 순서가 정해져있는데,
이대로라면 만약에 10 같은 경우는
10 - 5 - 4 - 2 - 1 이런 식으로 되겠죠? 하지만 10 - 9 - 3 - 1 요게 최소값입니다.
Dynamic programming 기법으로 푸는게 맞을거 같네요. youtube에 해당 기법 알고리즘 강의들 많이 있습니다.
참고하시면 될거 같아요 ^^
댓글을 작성하려면 로그인해야 합니다.
abbc0209 7년 전
1이 들어갈 수 없는 값들을 입력했을 때도 1이 뜨는데 초보라서 이유를 잘 모르겠네요
알고리즘 고수님들 도와주세요!!
import java.util.ArrayList;
import java.util.Scanner;
public class Main { //
static ArrayList<Integer> list = new ArrayList<>();
static int count=0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
makeOne(scanner.nextInt());
list.sort(null);
System.out.println(list);
}
public static void makeOne(int x){
int temp =x;
if(x==1){
list.add(count);
count=0;
return;
}
if(x%3==0){
count++;
makeOne(temp/3);
}
if(x%2==0){
count++;
makeOne(temp/2);
}
count++;
makeOne(temp-1);
}
}