Q1904. 01타일

dp[i-2]에 11, 00을 추가하면 dp[i]의 일부가 되며

dp[i-1]에 1을 추가하면 dp[i]의 일부가 됩니다.

따라서 dp[i] = dp[i-1] + dp[i-2]입니다.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q1904 { static long[] dp = new long[1000001]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int num = Integer.parseInt(st.nextToken()); dp[1] = 1; dp[2] = 2; for (int i = 3; i <= num; i++) { dp[i] = dp[i-2] + dp[i-1]; dp[i] %= 15746; } System.out.println(dp[num]); } }