백준 알고리즘 1904: 01타일(Java)

문제 풀이: 매번 느끼는거지만 동적계획법은 종이에 직접 적어가면서 규칙을 찾아가는 것이 중요하다고 생각합니다. 이 문제 또한 그렇게 풀다보면 규칙이 나오고 답을 쉽게 구할 수 있습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Sol_1904 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        long[] dp = new long[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3; i<=n; i++){
            dp[i] = (dp[i-2] + dp[i-1]) % 15746;
        }
        bw.write(dp[n]+"\n");
        bw.flush();
        br.close();
        bw.close();
    }
}