[백준 알고리즘] 14889번 스타트와 링크 (JAVA)

 

---

주의 사항

• 해당 문제는 두가지 유형으로 풀이가 가능하다.
  • DP
  • 완전 탐색 : n은 11보다 작기에 시간복잡도는 O(n!) = O(10!) = 3,628,800 (대략 40만) < 100,000,000 (1초) 이다.

 

---

코드 블럭

DP (다이나믹 프로그래밍)

package boj400;

import java.util.ArrayList;
import java.util.Scanner;

public class boj_9095 {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(scanner.nextInt());
        }

        int[] dp = new int[12];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        dp[4] = 7;

        for (int i = 5; i < 11; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

        for (int i = 0; i < list.size(); i++) {
            System.out.println(dp[list.get(i)]);
        }
    }

}

완전 탐색 (브루트 포스)

package boj530;

import java.util.ArrayList;
import java.util.Scanner;

public class boj_9095 {
    static int count = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(scanner.nextInt());
        }

        int[] arr = new int[]{1, 2, 3};

        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            // dfs 시작 1,2,3 배열로 list.get(i)를 만든다. depth는 list.get(i)까지 로..
            Integer num = list.get(i);
            // n -> num, r -> num, sum = 0
            dfs(arr, 0, 0, num, num);
            // count결과를 result에 넣어주고 count=0으로 초기화
            result.add(count);
            count = 0;
        }

        for (int i = 0; i < n; i++) {
            System.out.println(result.get(i));
        }
    }

    private static void dfs(int[] arr, int sum, int depth, Integer n, Integer r) {
        if (sum == n) {
            count++;
            return;
        }

        if (depth == r) {
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            dfs(arr, sum + arr[i], depth + 1, n, r);
        }
    }
}