[백준 1904 / JAVA] 01타일

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

1904번: 01타일

전에 풀었던 이친수와 비슷한 DP 문제이다.

 

0은 두개 연속와야 하는 경우를 생각해준다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        int N;
        int[][] dp;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dp = new int[2][N + 1];

        dp[1][1] = 1;
        dp[1][0] = 1;

        for (int i = 2; i <= N; i++) {
            dp[0][i] = (dp[1][i - 2] + dp[0][i - 2]) % 15746;
            dp[1][i] = (dp[1][i - 1] + dp[0][i - 1]) % 15746;
        }

        System.out.println(((dp[0][N] % 15746) + (dp[1][N] % 15746)) % 15746);

    }
}

dp[0]배열은 0이 오는 경우 dp[1] 배열은 1이 오는 경우이다.

0은 연속 두개가 와야 하므로  i-2 부분을 서로 더해주고 1은 아무거나 올 수 있으므로 i-1 부분을 더해준다.

%15746 하는 부분을 놓쳐 한번 틀렸다 주의해야 한다.