[백준]2193 이친수

package baekjoon;

import java.util.Scanner;

public class Main_2198 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        Long[][] dp = new Long[N+1][2];
        dp[1][0] = 0L;       // 한자리 수 중 0으로 끝나는 이친수 갯수
        dp[1][1] = 1L;       // 한자리 수 중 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[i-1][0]+" "+dp[i-1][1]);
        }

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

    }
}

풀이👩‍💻
이차원배열을 만들어서 인덱스 0번엔 N자리 수, 1번엔 0/1 로 끝나는 이친수의 갯수 로 지정했다.
비슷한 유형을 풀어봤어서 이번엔 접근하는게 어렵지 않았다!

dp[1][0] = 한자리 수 중 0으로 끝나는 이친수 갯수 = 0개 (0으로 시작할 수 없으므로)
dp[1][1] = 한자리 수 중 1로 끝나는 이친수 갯수 = 1개(1)

dp[2][0] = 두자리 수 중 0으로 끝나는 이친수 갯수 = 1개(10)
dp[2][1] = 두자리 수 중 1로 끝나는 이친수 갯수 = 0개(1이 연속으로 붙을 수 없으므로)

dp[3][0] = 1(100)
dp[3][1] = 1(101)
dp[4][0] = 2(1000 1010)
dp[4][1] = 1(1001)
dp[5][0] = 3(10000 10100 10010)
dp[5][1] = 2(10001 10101)
.
.

이렇게 쭉쭉 써나가다 보면
dp[N][0] = dp[N-1][0]+dp[N-1][1]
dp[N][1] = dp[N-1][0]
이라는 점화식을 얻을 수 있다!

문제 접근법이 맞았는데 나는 처음에 배열을 int로 선언해줘서 틀렸다.
배열을 int로 선언해주게 되면 49부터 음수값이 나온다.

0 1
1 0
1 1
2 1
3 2
5 3
8 5
13 8
21 13
34 21
55 34
89 55
144 89
233 144
377 233
610 377
987 610
1597 987
2584 1597
4181 2584
6765 4181
10946 6765
17711 10946
28657 17711
46368 28657
75025 46368
121393 75025
196418 121393
317811 196418
514229 317811
832040 514229
1346269 832040
2178309 1346269
3524578 2178309
5702887 3524578
9227465 5702887
14930352 9227465
24157817 14930352
39088169 24157817
63245986 39088169
102334155 63245986
165580141 102334155
267914296 165580141
433494437 267914296
701408733 433494437
1134903170 701408733
1836311903 1134903170
-1323752223 1836311903

왜냐하면 !
int 값의 범위는 –2,147,483,648 ~ 2,147,483,647 사이인데
49번째 0번 인덱스에 들어갈 값이 2971215073라 범위를 넘어버려서 계산이 제대로 안되기 때문이다.

Long으로 수정해주면 해결 ~
dp 실버3과 한발 가까워졌다 정답비율은 똥망이지만..