[백준 1904] 01타일

 

n 의 길이에 따라 만들 수 있는 이진수열의 수를 구해보면 피보나치 수열과 같다.

 

 

 

 

 

1. 동적계획법을 이용하여 배열을 채운다.

2. (A+B)%M = (A%M+B%M)%M 을 이용한다.

 

public static int f(int n) {
        if(n == 0) {dp[0] = 0; return 0;}
        if(n == 1) {dp[1] = 1; return 1;}
        if(n == 2) {dp[2] = 2; return 2;}
        if(dp[n] != -1) return dp[n];
        
        int result = f(n-2)%15746 + f(n-1)%15746;
        dp[n] = result;
        return result;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        for(int i=0; i<dp.length; i++)
            dp[i] = -1;
        
        System.out.println(f(n)%15746);
}

 

부 - (A+B)%M = (A%M+B%M)%M 증명

직접 썼다 ㅋㅋ