[백준] 1463번 : 1로 만들기 with python3, java

18 Aug 2018

Reading time ~1 minute

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

dp bottom up 풀이

D[i]는 D[i-1]를 만들 수 있는 경우의 수에 +1만 하면된다.
D[i//2], D[i//3] 도 마찬가지이다. 그래서 점화식을 사용해서 값을 구하고 해당 값으 array에 저장한다.
배열의 index가 숫자를 뜻하고 값이 그 indx(숫자)까지 도달할 때 최소 경우의 수를 뜻하다.

1.D[i]값은 D[i-1], D[i//2], D[i//3] 중에 가장 작은 값을 구한다.

그 후 그 값에서 경우의 수를 늘리는 것이니 +1을 하고 array에 넣는다.

참고 for문을 2에서 시작한다. 여기에서 시작하는 이유는 D[1], D[2], D[3]의 값을 1로 보내기 위해서 했다.

n = int(input())
D = [0]*(n+1)


# bottom-up
for i in range(2, n+1):
    if i%2 == 0 :
        D[i] = min(D[i-1]+1, D[i//2]+1)
    if i%3 == 0 :
        D[i] = min(D[i-1]+1, D[i//3]+1, D[i])
print(D[n])

# top-down
def go(n):
    if n == 1 :
        return 0
    if d[n] > 0 :
        return d[n]
    d[n] = go(n-1) + 1
    if n%2 == 0 :
        tmp = go(n//2) + 1
    if n%3 == 0 :
        tmp = go(n//3) + 1

    if d[n] > tmp:
        d[n] = tmp
    return d[n]
print(go(n))

top-down으로 풀면 python의 경우 콜스택이 터진다. 이는

import sys
sys.setrecursionlimit(1000011)

을 추가하면 급 메모리초과가 뜸으로 콜스택이 터졌다는 것을 알 수 있다. 이는 파이선이 tail_recursion_optimize가 안되서 인데 관련된 글은

https://joosjuliet.github.io/tail_recursion/ 여기있다.

public class Main {
    static Scanner s = new Scanner(System.in);
    static int[] D = new int[1000001];
    public static void main(String[] args) {
        int n = s.nextInt();
        D[1] = 0;

        for (int i = 2; i <= 1000000; ++i) {
            D[i] = D[i - 1]+1;

            if (i % 3 == 0 && D[i] > D[i/3] ) {
                D[i] = D[i/3] + 1;
            }else if (i % 2 == 0&& D[i] > D[i/2] ) {
                D[i] = D[i/2] + 1;
            }

        }

        System.out.println(D[n]);
    }
}

algorithm 백준