백준 11726번 2n 타일링 (실버3, DP) java, python

백준 11726번 링크

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        int[] dp = new int[1001];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i < N + 1; i++) {
          dp[i] = (dp[i - 2] + dp[i - 1]) % 10007;
        }
        System.out.println(dp[N]);
    }
}

여기서 모드를 나누는 것을 더하는데에 주목할 것.

임의의 정수 x에 대해
x = m+n 이라면
x/k = m/k+n/k 이므로
x%k = m%k + n%k 이다.

생각지 못했던 테크닉이다.