[2193번] 이친수의 개수 ( 2차원 배열 DP, DP 배열도 long으로 )

---

이 문제는 경우가 2가지다.
자리에 0을 두는 경우와 자리에 1을 두는 경우
앞에서는 1차원 배열 dp를 계속 생성했기 때문에 1차원 배열로 어떻게 점화식을 세워야 할지 고민했는데
2차원 배열로 두면 2가지 경우의 수에 대한 점화식을 생성할 수 있었다.

---

✅ 점화식

y축은 0과 1이다.

D[i][0] = i자리에서 끝이 0으로 끝나는 이친수의 개수
D[i][1] = i자리에서 끝이 1로 끝나는 이친수의 개수

이제 식의 정의를 내렸으니 수식만 세우면 되는데,
끝이 0으로 끝나려면 수식 앞이 1.0이 될 수 있고, 1로 끝나려면 앞이 0만 될 수 있다.
이걸 어떻게 세우지 싶었는데.!

D[i][0] = D[i-1][1] + D[i-1][0]
D[i][1] = D[i-1][0] 

이렇게 할 수 있는데 만약에 최종 6자리 이친수를 구해야 하면

D[5][0] + D[5][1] + 1

두 개로 나뉘고 각각 경우에서 1아니면 0이 될 수 있으니까 +1 필수.

한 번 바텀 업으로 구해볼까

---

✅ 코드

맞왜틀하고 있었는데, long 타입으로 선언하니까 통과했다..
아,, 90이면 자릿수가 90이니까 그럴만하다!

import java.util.Scanner;

public class Main {
	static long[][] dp;

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

		dp = new long[n + 1][2];

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

		for (int i = 2; i <= n; i++) {
			dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
			dp[i][1] = dp[i - 1][0];
		}

		System.out.println(dp[n][1] + dp[n][0]);

	}
}

---