[백준] 동적 계획법 (1904 : 01타일)

문제

---

https://www.acmicpc.net/problem/1904

1904번: 01타일

---

해설

---

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();

    static int arr[];

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());

        arr = new int[1000001];
        arr[1] = 1;
        arr[2] = 2;
        arr[3] = 3;

        sb.append(dp1904(N));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static int dp1904(int N){
        if(arr[N] == 0)
            arr[N] = (dp1904(N-1)+dp1904(N-2)) % 15746;
        return arr[N];
    }
}

N	1	2	3	4	5	6	7	8
1 (1)	1
2 (2)	11	00
3 (3)	111	100	001
4 (5)	1111	1100	1001	0011	0000
5 (8)	11111	11100	11001	10011	00111	00001	00100	10000

해당 표를 확인해보면 규칙을 발견할 수 있다.

N = 1 → 1

N = 2 → 2

N = 3 → 3

N = 4 → 5 (2 + 3)

N = 5 → 8 (3 + 5)

∴ arr[N] = arr[N-1] + arr[N-2] 이다.

따라서 이를 재귀함수로 구현하고, 이미 계산했던 값일 경우, 결과를 그대로 사용하도록 한다.

---

결론

---

어떻게 풀지 생각하다가, 각 경우를 확인해보았는데, 규칙성을 찾을 수 있어서 쉽게 해결할 수 있었따!.

---