0x10 - DP : BOJ2193 이친수

1. 2차원 배열을 쓴 경우

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        //1. 테이블설정
        //d[i][j] : 끝자리가 j인 i자리수의 이천수의 개수
        long[][] d = new long[n+5][2];

        //2. 초기화
        d[1][1] = 1; d[1][0] = 0;
        d[2][0] = 1; d[2][1] = 0;

        /*3. 점화식
        10
        100 101
        1000 1001 1010
        10000 10001 10010 10100 10101
        d[3][0] = d[2][0] + d[2][1]; d[3][1] = d[2][0];
        */
        for (int i = 3; i <= n; i++) {
            d[i][0] = d[i-1][0] + d[i-1][1];
            d[i][1] = d[i-1][0];
        }
        // 4. 출력
        System.out.println(d[n][0] + d[n][1]);
    }
}

1. 테이블 설정
   d[i][j] : 끝자리가 j인 i자리수의 이천수의 개수
2. 초기화
3. 점화식
   d[i][0] : d[i-1][0]이나 d[i-1][1]에 0을 붙이기 / d[i][1] : d[i][1]에 1붙이기

---

2. 1차원 배열

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        //1. 테이블설정
        //d[i] : i자리수의 이천수의 개수
        long[] d = new long[n+5];

        //2. 초기화
        d[1] = 1; d[0] = 0;
        d[2] = 1;

        /*3. 점화식
        10
        100 101
        1000 1001 1010
        10000 10001 10010 10100 10101
        d[i-1]에 0을 붙이거나 / d[i-2]에 01을 붙이거나 = 피보나치
        */
        for (int i = 3; i <= n; i++) d[i] = d[i-1]+d[i-2];
        // 4. 출력
        System.out.println(d[n]);
    }
}

1. 테이블 설정
   d[i] : i자리수의 이천수의 개수
2. 초기화
3. 점화식
   d[i-1]에 0을 붙이거나 / d[i-2]에 01을 붙이거나 = 피보나치

---

근데 결국 (d[i][1] = d[i-1][0]에 1을 붙이기) == (d[i-2]에 01을 붙이기) 라서 같은 방식이다
시간적으로는 아예 차이가 없었고, n이 작아서 따깋 메모리로도 큰 차이가 없어보이긴 하지만, 어쨋든 2번이 보기에도 훨씬 간결하고, 메모리적으로도 효율적인 것 같다