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);
    }
}

aod0326   7년 전

우선 그 문제보다는 알고리즘 상에 문제가 있어보입니다. 

3으로 나눠지면 먼저 3으로 나누고 

아니면 2, 아니면 1 이런식으로 순서가 정해져있는데, 

이대로라면 만약에 10 같은 경우는 

10 - 5 - 4 - 2 - 1     이런 식으로 되겠죠? 하지만 10 - 9 - 3 - 1 요게 최소값입니다.

Dynamic programming 기법으로 푸는게 맞을거 같네요. youtube에 해당 기법 알고리즘 강의들 많이 있습니다.

참고하시면 될거 같아요 ^^

댓글을 작성하려면 로그인해야 합니다.