[백준]1304 01타일

package baekjoon;

import java.util.Scanner;

public class Main_1904 {
    static long[] dp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        dp = new long[10000001];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] =2;
        for (int i = 3; i <= N; i++) {
            dp(i);
        }
        System.out.println(dp[N]);
    }
    public static void dp(int i) {
        dp[i] = (dp[i-1]+dp[i-2])%15746;
    }
}

👩‍💻풀이
문제 자체는 쉬웠다! (일일이 써보면 쉽다..)
1 1
2 11 00
3 1(00) 11(1) 00(1)
4 11(00) 00(00) 100(1) 111(1) 001(1)
5 100(00) 111(00) 001(00) 1100(1) 0000(1) 1001(1) 1111(1) 0011(1)
.
.
.
보면 n-1에는 00 타일을 붙이고 n-2에는 1타일을 붙이면 n 길이의 이진수를 만들 수 있는 개수가 나온다는 규칙을 찾을 수 있다. (1, 2, 3 더하기와 비슷한 유형인 것 같다.)
점화식 찾기까진 쉬웠는데 왜 계속 틀렸냐하면 ..

1. 15746을 최종 출력 때 나누어 줬다.
2. 배열 초기화를 N+1로 시켜줬다.

1번의 답은 연산을 구하는 과정에서 int나 long의 범위를 벗어나서 계속 나머지 연산을 해준 값을 저장해주어야 맞다고 한다. 나는 처음에 int의 범위가 벗어나서 long으로 바꿔주면 최종 출력 때만 나머지 연산을 해주면 된다고 생각했는데 그냥 둘다 벗어나기 때문에 자료형 상관없이 계속 나머지 연산을 한 값을 저장해주면 됐다.

2번의 원인은 N이 1일 경우에 있다. N이 1이라면 배열의 사이즈는 0,1 총 2일텐데 초기값을 설정해주는 부분에서 dp[2]에 접근하려고 하니 인덱스 에러가 난 것이다.

끄읏 ~~