1904. 01타일

1. 문제 분석
    1) '1'과 '00'이라는 숫자를 조합해서, N자리 수를 만들 수 있는 모든 가짓수를 구한다.
    ex. N=1이면 '1' 하나만 만들 수 있고, N=2이면 11 또는 00만 만들 수 있다.
    2) 가짓수를 15746으로 나눈 나머지를 구한다.

2. 제약 조건
    1) 1 <= N <= 1,000,000

3. 의사결정
    1) '00'으로 채울 수 있는 숫자의 최대부터 구하면 될 듯?
    2) N을 받는다.
    3) 일단 몇개 반복해보면..

    N=1 : 1
    N=2 : 11 00
    N=3 : 111 001 100
    N=4 : 1111 1100 1001 0011 0000
    N=5 : 11111 11100 11001 10011 00111 10000 00100 00001
    N=6 : 111111 111100 111001 110011 100111 001111 110000 100100 100001 001001 001100 000011 000000

    개수 : 1 2 3 5 8 13
    1 + 2 = 3
    2 + 3 = 5
    3 + 5 = 8
    5 + 8 = 13
    N-2 + N-1 = N이라는 규칙이 생긴다!

 

---

1. DP(Bottom-up)로 풀어보자.

 N의 개수만큼 배열을 만든다.
처음 2개는 수동으로 넣는다.
3번째부터는 이전 두개 값을 더한 값을 넣는다.
15746으로 나눈 나머지를 출력한다
           
문제풀면서 수정한 부분
    1)  3까지 하드코딩하면 안된다! 2까지 하드코딩하되 N+1로 만들기.
    2) for문 바깥에서 출력 직전에 %15746을 했더니 int값을 넘어버린다.
       for문에서 계산할 때부터 %를 한 값을 배열에 넣자.
    3) 테스트케이스를 여러개 시도해보자..

 import java.io.*;

 import java.util.*;

 public class App {

    public static void main(String[] args) throws IOException {

        // N 받기

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        // N만큼 배열 만들기

        int[] arr = new int[N+1];

        // 수동으로 넣기

        arr[0] = 1;

        arr[1] = 2;

        // 자동증가시키기

        for (int i = 2; i <N; i++) {

            arr[i] = (arr[i-2] + arr[i-1]) % 15746;

        }

        // N값을 나눠서 출력하기

        System.out.println(arr[N-1]);

    }

 }

 

 

---

2. 재귀를 사용한 메모이제이션 방식(Top-down DP)으로도 풀어보자.

 import java.io.*;

public class Main {

    static int[] memo;

    static final int MOD = 15746;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        // 배열 생성

        memo = new int[N + 1];

        // 정답 출력

        System.out.println(dp(N));

    }

    // 재귀적 DP

    static int dp(int n) {

        if (n == 1) return 1;

        if (n == 2) return 2;

        // 이미 계산된 값이면 바로 반환

        if (memo[n] != 0) return memo[n];

        // 계산 후 저장

        return memo[n] = (dp(n - 1) + dp(n - 2)) % MOD;

    }

}

재귀 방식에서 5배의 메모리, 2배의 시간이 소요되었다.