[백준] 1904번 01타일

1904번: 01타일

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[1000001];
        arr[1] = 1;
        arr[2] = 2;
        for (int i = 3; i < 1000001; i++) {
            arr[i] = arr[i - 2] + arr[i - 1];
        }
        System.out.print(arr[n] % 15746);
    }
}

이렇게 했는데 자꾸 틀렸다는거다

아무리 봐도 맞는데 뭐가 틀리다는건지 몰라서 너무 답답했지만 그래도 스스로 풀어내겠다는 오기로 풀었다

그런데도 계속 틀리다는거다

그래서 결국 구글링을 해봤더니 다들 저장할 때부터 15746으로 나눈 나머지를 저장하더라

설마 하고 똑같은 코드에 % 15746 이것만 붙여서 했더니 맞았다고 떴다.

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[1000001];
        arr[1] = 1;
        arr[2] = 2;
        for (int i = 3; i < 1000001; i++) {
            arr[i] = arr[i - 2] % 15746 + arr[i - 1] % 15746;
        }
        System.out.print(arr[n] % 15746);
    }
}

너무 허무했다.

길이가 N인 2진 수열의 개수를 15746으로 나눈 나머지를 출력하라고 해서 출력할 때만 15746으로 나눈 나머지를 출력했는데 왜 저장할 때도 15746으로 나눈 나머지를 저장해야 하는지 모르겠었다.

그런데 생각해보니 피보나치 수열은 기하급수적으로 증가하기 때문에 오버플로우가 난다.

int로 하면 47번째부터, long으로 해도 93번째부터 오버플로우가 난다.

따라서 애초에 저장할 때 나머지를 저장해주어 오버플로우를 방지한 것이다.

몇 분만에 푼 문제를 괜히 몇 시간 시간낭비했다는 생각이 들었었지만 덕분에 깨달은 게 있으니 다행인 것 같다. 다음부턴 이런 실수 하지 말아야지.