백준) - 1로 만들기 (재귀함수) / JAVA

문제 출저 입니다.

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

사고의 흐름

 

일단 규칙성을 찾기 위해 1부터 15까지의 경우의 수를 찾아 보았다.  모든 경우의 수를 찾고 그 중 횟수의 최솟값을 찾는 방법을 사용하였더니 가지 치기 방법과 관련하여 고민하였다. 하지만 가지치기로 생각을 하니 숫자가 점점 더 커지면 경우의 수는 기하급수적으로 늘어났다. 즉 틀린 방법이었다.

 

다른 방법을 고민하다가 규칙성을 발견하였다. 예를 들면 6은 6>>2>>1이 최솟값인데 12를 보면 12>>6>>2>>1이 최솟값이기 때문이다. 즉, 6이 반복됨을 발견할 수 있었다. 

 

해결방법

package backjoon;
import java.util.*; //Scanner를 사용하기 위해
 
 
public class Beak1463{
 
    static int[]answer;
    public static void main(String[]args){
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        answer=new int[n+1];
        System.out.println("answer"+answer);
        System.out.println(solution(n));
        scan.close();
    }
 
    static int solution(int n){     //
        if(n==1) return 0;  //1은 어떤 방법을 하지 않아도 1이기 때문이다.
        if(answer[n]>0) return answer[n];
 
        answer[n]=solution(n-1)+1;  //원하는 값은 answer이고, 가장 최소의 값인 answer를 도출하기 위한 함수가 solution메소드 이다. 
        
        if(n%2==0){
            int tmp=solution(n/2)+1;//12는 6의 최솟값에 1을 더한 값이 최소이므로  
            if(answer[n]>tmp) answer[n]=tmp;
            //anwer[n]은 위에서 말한 solution(n-1), 예를 들어 8을 생각해보자
            //8을 2로 나누면 4, 즉 8>>4>>2>>1로 횟수는 3이다
            //반면 8에서 1을 빼면 8>>7>>6>>2>>1로 횟수는 4이다
            //이처럼 4>3이므로 8을 최소의 횟수동안 1로 만들려면 2로 나눠야 하므로 바꾸어 준다.
        }
 
        if(n%3==0){
            int tmp=solution(n/3)+1;
            if(answer[n]>tmp) answer[n]=tmp;
            //위에서 처럼 생각하면 됨
        }
 
        return answer[n];//이로 인해 가장 최소의 answer값이 return됨.
    }
}

 

결과

 

느낀점

역시 많은 문제를 풀어봐야겠다. 많은 문제를 풀고 많은 풀이과정을 배워야겠다.