JAVA)2193번 이친수 - 다이나믹 프로그래밍

1. Top-Down 방식

import java.util.*;

public class Main {
    static long A[][]; // n자리의 이친수의 개수를 저장하는 배열
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        A = new long[num+1][2];
        pinaryNum(num);
        System.out.println(A[num][0] + A[num][1]);
    }

    public static void pinaryNum(int n) {
        // Top-Down 방식
        // A[i][j] = 마지막 자리 숫자가 j인 i자리 이친수의 개수
        // 점화식 : A[n] = A[n][0] + A[n][1]
        //         A[n][0] = A[n-1][0] + A[n-1][1] (0은 0 또는 1 모두 앞에 올 수 있음)
        //         A[n][1] = A[n-1][0] (1은 0 앞에만 올 수 있음)
        // 이전 자리수가 0으로 끝나면 0또는 1 두가지 경우가 올 수 있지만
        // 전 자리수가 1로 끝나면 0밖에 올 수 없다. (한가지 경우만 존재) (끝에 10을 하나로 묶어서 생각할 수 있다 -> A[n-2]에 붙인다고 생각)
        if (n < 2) {
            A[1][1] = 1;
            return;
        }
        if (A[n-1][0] == 0 && A[n-1][1] == 0) {
            pinaryNum(n-1);
        }
        A[n][0] = A[n-1][0] + A[n-1][1];
        A[n][1] = A[n-1][0];
    }
}

2. Bottom-Up 방식

import java.util.*;

public class Main {
    static long A[][]; // n자리의 이친수의 개수를 저장하는 배열
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        A = new long[num+1][2];
        pinaryNum(num);
        System.out.println(A[num][0] + A[num][1]);
    }

    public static void pinaryNum(int n) {
        // Bottom-Up 방식
        // A[i][j] = 마지막 자리 숫자가 j인 i자리 이친수의 개수
        // 점화식 : A[n] = A[n][0] + A[n][1]
        //         A[n][0] = A[n-1][0] + A[n-1][1] (0은 0 또는 1 모두 앞에 올 수 있음)
        //         A[n][1] = A[n-1][0] (1은 0 앞에만 올 수 있음)
        A[1][1] = 1;
        for (int i=2;i<n+1;i++) {
            A[i][0] = A[i-1][0] + A[i-1][1];
            A[i][1] = A[i-1][0];
        }
    }
}

 

# memorization을 일차원 배열로 해결하기 - 이친수 문제는 고려할 경우의 수가 0 또는 1로 두가지 밖에 없으므로 1차원 배열로도 다이나믹 프로그래밍을 수행할 수 있다.

 

1. Top-Down

import java.util.*;

public class Main {
    static long A[]; // n자리의 이친수의 개수를 저장하는 배열 (일차원 배열로 해결하기
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        A = new long[num+1];
        pinaryNum(num);
        System.out.println(A[num]);
    }

    public static void pinaryNum(int n) {
        // Bottom-Up 방식
        // A[i][j] = 마지막 자리 숫자가 j인 i자리 이친수의 개수
        // 점화식 : A[n] = A[n-1] + A[n-2]
        //         A[n-1] : 전 이진수가 0으로 끝나는 경우 -> 마지막 자리에 0, 1 모두 올 수 있음
        //         A[n-2] : 전 이진수가 1로 끝나는 경우 -> 마지막 자리에 0 밖에 올 수 없음
        //                  01을 한 묶음으로 생각해서 A[n-2]에 01을 추가한 경우를 생각하면 됨
        if (n < 2) {
            A[1] = 1;
            return;
        }
        if (A[n-1] == 0) {
            pinaryNum(n-1);
        }
        A[n] = A[n-1] + A[n-2];
    }
}

2. Bottom-Up

import java.util.*;

public class Main {
    static long A[]; // n자리의 이친수의 개수를 저장하는 배열 (일차원 배열로 해결하기
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        A = new long[num+1];
        pinaryNum(num);
        System.out.println(A[num]);
    }

    public static void pinaryNum(int n) {
        // Bottom-Up 방식
        // A[i][j] = 마지막 자리 숫자가 j인 i자리 이친수의 개수
        // 점화식 : A[n] = A[n-1] + A[n-2]
        //         A[n-1] : 전 이진수가 0으로 끝나는 경우 -> 마지막 자리에 0, 1 모두 올 수 있음
        //         A[n-2] : 전 이진수가 1로 끝나는 경우 -> 마지막 자리에 0 밖에 올 수 없음
        //                  01을 한 묶음으로 생각해서 A[n-2]에 01을 추가한 경우를 생각하면 됨
        A[1] = 1;
        for (int i=2;i<n+1;i++) {
            A[i] = A[i-1] + A[i-2];
        }
    }
}