[백준]1904. 01타일

📄 링크

01타일

---

💡 문제 분석

입력 N이 100만으로 꽤 큰 숫자입니다. 기존 숫자에서 00을 더할지 1을 더할지를 선택하는 방법으로 메모이제이션을 사용했었는데 재귀로 문제를 풀면 스택 오버 플로가 발생하였습니다.

어쩔 수 없이 반복적 dp를 사용하였습니다.

덧셈을 할 때 계속 15746으로 나누어 주지 않으면 오버플로가 발생하게 됩니다

---

⌨️ 코드

import java.util.Scanner;

public class _1904_01타일 {
    static int[] cache = new int[1000001];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        cache[1] = 1;
        cache[2] = 2;
        for(int i = 3; i <= N; i++) {
            cache[i] = (cache[i - 1] + cache[i - 2]) % 15746;
        }
        System.out.println(cache[N] % 15746);
    }
}

---

📋 회고

• 100만 정도 dp가 되니 재귀로는 안되는구나
• mod 중간에 계속 해주자