문제

정수 a를 k로 만들기

풀이

이것은 시간초과 코드

		Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{a,0});
        while (q.peek()[0] != k) {
            int[] x = q.poll();
            q.add(new int[] {x[0] + 1, x[1]+1});
            q.add(new int[] {x[0] * 2, x[1]+1});
        }
        System.out.println(q.poll()[1]);

연산을 무한정 해야하기 때문에 결코 좋은 코드가 아님..
어떻게 하면 나눗셈과 덧셈을 적게 할 수 있을까. 2를 하는게 가장 빨리 닿을 수 있는 횟수라 제일 먼저 2를 해야한다. 그렇기 때문에 필요없는 연산을 줄이기 위해 memoriaztion 을 할수 있는 boolean 배열을 사용한다.

		while (!q.isEmpty()) {
            int[] x = q.poll();
            if (x[0] == k) {
                System.out.println(x[1]);
                return;
            }
            if (x[0] * 2 <= k) {
                check[x[0] * 2] = true;
                q.add(new int[] {x[0] * 2, x[1]+1});
            }

            if (!check[x[0]+1]) {
                q.add(new int[] {x[0] + 1, x[1]+1});
            }
        }

초콜릿 컵 때도 그랫지만... 연산이 많아지면 아주 버거워 한다 아주 단순한 연산처럼 보여도 메모리를 아주 많이 먹는것 같다
일단 연산 횟수를 줄이는 방법을 무조건 생각해야 한다

전체 코드

전체 코드