백준 1463번: 1로 만들기 [Java/Kotlin]

//in java
class Result{
	/**
	문제
	정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

	X가 3으로 나누어 떨어지면, 3으로 나눈다.
	X가 2로 나누어 떨어지면, 2로 나눈다.
	1을 뺀다.
	정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

	입력
	첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

	출력
	첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
	**/
	
	public int calculate(int val) {
		
		int table[] = new int[val+1];
	    table[0] = 0;
	    
	    for(int i=1; i<=val; i++) {
	    	table[i] = table[i-1] + 1;
	    	if(i%2 == 0) {
	    		table[i] = Math.min(table[i], table[i/2]+1);
	    	}
	    	if(i%3 == 0) {
	    		table[i] = Math.min(table[i], table[i/3]+1);
	    	}
	    }
	    
		return table[val] - 1;
	}
}

//in kotlin
fun calculate(answer_: String): String {

        val answer = answer_.toInt()

        val table = Array(answer+1) { i -> i }
        table[0] = 0

        for (i in 1 .. answer) {
            table[i] = table[i - 1] + 1
            if (i % 2 == 0) table[i] = table[i].coerceAtMost(table[i / 2] + 1)
            if (i % 3 == 0) table[i] = table[i].coerceAtMost(table[i / 3] + 1)
        }

        val result = table[answer] - 1

        return result.toString()
    }

첫 시도에 많이 헤멨다.

 

갈피를 잡지 못했던 이유는 큰 수 에서부터 나누어야 하겠지? 라는 생각 이었다.

 

주어진(입력한 수) 수 를 기준으로 Max 에서 나누기 시작하면 특정 수 에서 프로그램이 오작동을 일으키게 된다.

(정확히는 오작동이 아니라 생각의 맹점이고, 프로그램은 코딩대로 돌아간다.)

 

예를 들면 11 을 입력 받았을 때, 출력되어야 하는 결과 값은 4 이다.

 

case 1 정상 : (입력 11) 11 -> 10 -> 9 -> 3 -> 1  (4회)

case 2 맥스 값에서 나누는 경우 : (입력 11) 11 -> 10 -> 5 -> 4 -> 2 -> 1  (5회)

 

맥스 값에서 나누는 경우 위의 case2에 직면 할 가능성이 높다.

 

간단한 점화식을 세우고, 아래에서 부터 기입하여 계산 한다는 식으로 코딩하면 쉽게 풀 수 있다.

 

더 나은 알고리즘이 있을 수 있겠지만, 각 테이블 A[n] 에 기입되는 최소 연산횟수는

 

- 1 <= n 일 때, A[n] 은 0

- 2 <= n 일 때, A[n] 은 

              1) 2혹은 3의 배수가 아닌 경우, A[n-1] + 1

              2) 2의 배수 인 경우, A[n] 혹은 A[n/2]+1 중 최솟값 

              3) 3의 배수 인 경우, A[n] 혹은 A[n/3]+1 중 최솟값 

 

으로 정의 된다.