[백준 1463, Java] 1로 만들기

문제

www.acmicpc.net/problem/1463

1463번: 1로 만들기

check

* 두번째  풀이 외우기 

 

1. 처음 푼 풀이 (단순재귀)

 - 모든 경우의 수를 재귀를 이용해서 풀었다. 

 - 이때의 시간 복잡도는 모든 수가 3, 2로 나누어 떨어진다고 했을때 하나의 함수가 3개의 함수를 호출하게 된다. 따라서 3의 N-1 제곱이 되고 입력의 최대는 10의 6제곱이니까 시간초과가 나게 된다. 

 

check 

- 위 문제는 최소의 값을 구하는 거다. 따라서 함수를 호출하였을때 연산횟수가 이전에 호출했던 함수의 연산횟수보다 크면 다시 호출할 필요가 없다. 

위의 경우에 (2,1)을 호출했으면 (2,3)을 호출할 필요가 없는데 호출하게된다. 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static int minCount = 1000000;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        makeOne(N,0);
        bw.write(String.valueOf(minCount));
        bw.flush();
        br.close();
        bw.close();
    }

    //N : 연산 후 현재 N 의 값
    //count : 현재까지 연산 횟수
    public static void makeOne(int N, int count){
        if(N ==1){
            minCount = Math.min(count, minCount);
            return;
        }
        else if(N <1){
            return;
        }
        else{
            if(N%3==0){
                makeOne(N/3, count+1);
            }
            if(N%2==0){
                makeOne(N/2, count+1);
            }
            makeOne(N-1, count+1);
        }

    }
}

 

2. 틀린풀이2

- 2020.11.23 아직 점화식을 세우는 걸 잘 못한다

- 단순재귀로 풀면 시간초과가 날테니, 무언가를 기록해야한다는 것 까지는 생각을 했는데, 무엇을 기록해야할지에 대해 감이 오지 않았다. 그래서 한번 호출했던 것을 기록하기 위해 boolean 배열을 선언하고 N에 대해서 이전에 호출했으면 다시 호출하지 않도록 했다.

- 그런데 이렇게 하게되면 N = 1000000 인경우, N-1을 호출하는 것 때문에 StarckOverFlowStackOverflowError가 난다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public static int N;
	public static int minCount = 1000000;
	public static boolean[] isCalculated;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine().trim());
		isCalculated = new boolean[N+1];
		getOne(N,0);
		
		bw.write(String.valueOf(minCount));
		bw.flush();
		
		
		br.close();
		bw.close(); 
		
	}
	public static void getOne(int n, int count) {
		if(n==1) {
			minCount = Math.min(minCount, count);
		}
		else if(isCalculated[n]) {
			return;
		}
		else {
			isCalculated[n] =true;
			
			if(n%3==0) {		
				getOne(n/3, count+1);
			}
			if(n%2==0) {		
				getOne(n/2, count+1);
			}
			getOne(n-1, count+1);
		}
		
	}

}

 

 

 

3. 다이나믹 프로그래밍

 - 문제에 힌트가 나와있다. N -> N/3 N -> N/3 N -> N-1 로 문제의 크기가 작아진다. 따라서 "큰문제의 답을 작은 문제의 해를 이용해서 푼다" 는 다이나믹 프로그래밍을 이용해서 풀 수 있다. 

- 위의 문제를 점화식으로 나타내면 f(N) = min(f(N/3), f(N/2), f(N-1))+1 로 풀 수 있다.

- 이때 반복문을 이용해서 풀거나 재귀를 이용해서 풀 수 있다. 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static int[] memo;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine().trim());
        memo = new int[1000001];
        TopDown(N);

        bw.write(String.valueOf(memo[N]));
        bw.flush();

        br.close();
        bw.close();

    }

    public static void bottomUp(int N){
        for(int num =2; num<= N; num++){
            memo[num] = memo[num-1] +1;

            if(num%3 ==0 && memo[num]>memo[num/3]+1){
                memo[num] = memo[num/3]+1;
            }
            if(num%2 ==0 && memo[num]>memo[num/2]+1){
                memo[num] = memo[num/2]+1;
            }
         }
    }

    public static int TopDown(int N){
        if(N<=1){
            return N;
        }
        if(memo[N]>0){
            return memo[N];
        }

        memo[N] = TopDown(N-1)+1;
        if(N%3==0){
            int count = TopDown(N/3) +1;
            if(memo[N]> count) memo[N] =count;
        }
        if(N%2==0){
            int count = TopDown(N/2) +1;
            if(memo[N]>count) memo[N] =count;
        }
        return memo[N];
    }
}