백준 알고리즘: 1465번 1로 만들기

문제 정보

---

 

1463번: 1로 만들기

 

핵심

---

효율적인 알고리즘의 구현

풀이는 두가지 방식으로 진행해 보았다

- BFS(Breath First Search)

- DP(Dynamic Programming) - Bottom-up 방식

 

이 문제를 풀이하는데에 더욱 효율적인 알고리즘은 DP였으며 많이 접하지 못했던 유형이라 언제 이러한 알고리즘을 적용시켜야 하는지에 대해서 알게 되었던 것 같다

추가로 Top-down 방식의 풀이도 존재하는데, 더 효율적인 풀이가 있을 것 같아서 이에 대해서는 공부를 좀 더 하고 올리려고 한다

 

풀이

---

1. BFS를 활용한 풀이

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int number = Integer.parseInt(br.readLine());
        boolean[] visited = new boolean[number + 1];
        int result = BFS(number, visited);
        System.out.println(result);
    }

    public static int BFS(int start, boolean[] visited) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(start, 0));
        visited[start] = true;

        while (!queue.isEmpty()) {
            Node popItem = queue.poll();
            int value = popItem.value;
            int depth = popItem.depth;

            if (value == 1)
                return depth;

            if (value % 3 == 0 && !visited[value / 3])
                queue.add(new Node(value / 3, depth + 1));
            if (value % 2 == 0 && !visited[value / 2])
                queue.add(new Node(value / 2, depth + 1));
            if (value > 1 && !visited[value - 1])
                queue.add(new Node(value - 1, depth + 1));
        }
        return -1;
    }
}


class Node {
    int value;
    int depth;

    public Node(int value, int depth) {
        this.value = value;
        this.depth = depth;
    }
}

Node 클래스를 define하고, instance variable은 값과 깊이(level)을 두었다

여느 BFS 풀이와 다를 것 없이, Queue를 활용하여 빼고 방문하지 않은 노드를 골라 Queue에 다시 집어넣으면서

value가 1에 다다르면 depth를 리턴해주는 방식으로 풀이하였다

 

2. DP(Bottom-Up)

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int number = Integer.parseInt(br.readLine());
        int[] dp = new int[number + 1];

        for (int i = 2; i <= number; i++) {
            // default case
            dp[i] = dp[i - 1] + 1;
            // divide with 3
            if (i % 3 == 0)
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            // divide with 2
            if (i % 2 == 0)
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
        }
        System.out.println(dp[number]);
    }
}

코드의 길이도 줄고, 소요시간도 줄었다

피보나치 수열을 이 알고리즘을 이용해 풀었던 문제와 비슷하게 접근방식은 다음과 같다

 

사전지식

- dp[n]: n을 1로 만드는 데에 걸리는 최소 연산 횟수

- dp[0], dp[1] 은 이미 도달해 있기 때문에 value는 0이다

 

풀이방법

기본적인 경우(1을 빼는 연산)에는 dp[i] = dp[i-1] + 1 과 같다

- i를 만드는 최소 연산은, i-1을 만드는 최소 연산 횟수인 dp[i-1]에 1을 더하는 연산(+1)  을 해주는 것과 같다

 

3으로 나누어지는 경우라면 dp[i] = Math.min(dp[i], dp[i/3] + 1)과 같다

- i를 만드는 최소 연산은, 현재까지 구한 최소 연산인 dp[i] (1을 빼는 연산에서 넣어준 값) 과 dp[i/3] + 1 의 최소값과 같다

- dp[i/3] 은 i/3 이 1이 되기 위한 최소 연산 횟수이며, 여기에 3을 곱해주면 N이 되므로 (+1) 이다

 

2로 나누어지는 경우에도 위와 동일하다

 

 

고찰

---

Top-Down 방식을 사용한 풀이는 다음과 같았다

import java.io.*;
import java.util.*;

class Main {
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int number = Integer.parseInt(br.readLine());
        dp = new int[number + 1];

        System.out.println(makeOne(number));
    }

    public static int makeOne(int number) {
        if (number <= 1)
            return 0;

        if (number % 6 == 0) {
            return dp[number] = Math.min(makeOne(number / 3) + 1, makeOne(number / 2) + 1);
        } else if (number % 3 == 0) {
            return dp[number] = Math.min(makeOne(number / 3) + 1, makeOne(number - 1) + 1);
        } else if (number % 2 == 0) {
            return dp[number] = Math.min(makeOne(number / 2) + 1, makeOne(number - 1) + 1);
        } else {
            return dp[number] = makeOne(number - 1) + 1;
        }
    }
}

하지만, 시간초과가 발생하여 정상적인 풀이가 아님을 확인하였고, 이를 보완하여 수정하도록 하겠다

 

Source Code on GitHub

---