동적계획법1(2748, 1003, 1904, 9461)

[피보나치 수2 _ 2748]

 

 

* 조건

1. 입력된 n의 값을 피보나치 수를 통해 구한다

* 알고리즘

- 재귀 or DP

 

* 로직(Logic)

- dp[i] = dp[i-2] + dp[i-1] 점화식을 적용한다

 

import java.util.Scanner;

public class Problem_2748 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long[] dp = new long[n+1];

        dp[0] = 0;
        dp[1] = 1;

        for(int i=2; i<=n; ++i){
            dp[i] = dp[i-2] + dp[i-1];
        }
        System.out.println(dp[n]);
    }
}

 

[피보나치 함수 _ 1003]

 

 

* 조건

1. 메모이제이션을 고려하여 입력된 n에 대한 값을 구하는 과정을 거친다
2. 재귀 or DP를 거치면서 호출된 0과 1의 카운팅을 출력한다

* 알고리즘

- 재귀 or DP

 

* 로직(Logic)

- n의 값에 따라 0과 1이 카운팅되는 개수가 각각 피보나치 수열이 적용되는 것을 활용한다

- dp[2][n+1]로 설정해 0의 개수와 1의 개수 카운팅을 구별짓는다

- dp[0][i] = dp[0][i-2] + dp[0][i-1]과 dp[1][i] = dp[1][i-2] + dp[1][i-1] 점화식을 통해 개수를 구한다

 

import java.util.Scanner;

public class Problem_1003 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();

        int t=1;
        while (t <= testCase){
            int n = scanner.nextInt();
            int[][] dp = new int[2][n+1];

            doFibo(n, dp);
            t++;
        }
    }

    private static void doFibo(int n, int[][] dp) {
        if(n == 0) {
            System.out.println("1 0");
            return;
        }
        if(n == 1) {
            System.out.println("0 1");
            return;
        }

        //0과 1의 개수 dp
        dp[0][0] = 1;
        dp[0][1] = 0;

        dp[1][0] = 0;
        dp[1][1] = 1;

        for(int i=2; i<=n; ++i){
            dp[0][i] = dp[0][i-2] + dp[0][i-1];
            dp[1][i] = dp[1][i-2] + dp[1][i-1];
        }
        System.out.println(dp[0][n] + " " + dp[1][n]);
    }
}

 

[01타일 _ 1904]

 

 

* 조건

1. 0은 짝을 지어야 하고, 1은 상관없다
2. 길이 N으로 만들 수 있는 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다

* 알고리즘

- 재귀 or DP

 

* 로직(Logic)

- n의 값에 따라 만들 수 있는 2진 수열의 개수는 피보나치 수열의 공식을 갖고있다.

- dp[i] = dp[i-2] + dp[i-1] 점화식을 활용하여 답을 구한다

 

import java.util.Scanner;

public class Problem_1904 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] dp = new int[n+1];
        int divide = 15746;

        dp[1] = 1;
        dp[2] = 2;

        for(int i=3; i<=n; ++i){
            dp[i] = (dp[i-2] + dp[i-1]) % divide;
        }
        System.out.println(dp[n]);
    }
}

 

[파도반 수열 _ 9461]

 

 

* 조건

1. p(n)은 n번째 삼각형의 변의 길이를 뜻한다
2. 입력된 n에 맞는 변의 길이를 출력한다

* 알고리즘

- 재귀 or DP

 

* 로직(Logic)

- 변의 길이를 더 늘려보며 수를 구해보면

-> 1 1 1 2 2 3 4 5 7 9 12 16 21 28 ... 을 얻을 수 있다

- 규칙을 찾아보면 dp[i] = dp[i-3] + dp[i-2]가 성립된다는 것을 알 수 있고, 이를 활용해 DP를 적용하면 해결된다

 

import java.util.Scanner;

public class Problem_9461 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();

        int t=1;
        while (t <= testCase){
            int n = scanner.nextInt();
            long[] dp = new long[n+1];

            doProcess(n, dp);

            t++;
        }
    }

    private static void doProcess(int n, long[] dp) {
        if(n <= 3) {
            System.out.println(1);
            return;
        }

        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 1;
        for(int i=4; i<=n; ++i){
            dp[i] = dp[i-3] + dp[i-2];
        }
        System.out.println(dp[n]);
    }
}

 

DP를 활용하는 문제의 경우, 메모이제이션을 통해 일반 재귀를 사용했을 때의 시간 소요를 절감할 수 있다는 부분을 다시 한번 상기할 수 있었던 시간이었다. 상향식 방법을 사용해봤는데 직관적인 면은 있었지만, 점화식의 관계나 상황에 맞게 재귀 방식도 사용하는 것도 좋다는 생각을 했다.

 

또한 점화식을 통해 값을 누적될 때 int 타입을 벗어나는 경우도 있기 때문에 long과 같은 타입을 고려하는 습관도 필요하다고 생각했다.