[실버 3] [Java] 백준 11727번: 2xn 타일링 2

아이디어

저번에 풀었던 2xn 타일링 문제와 거의 같은 문제이다.

똑같이 dp를 사용하면 되는 문제이지만, 점화식이 좀 다르다.

 

이번에는 다음과 같은 규칙을 따른다

우리가 구하고 싶은 N번째 열에 타일을 채우는 방법이

N-1번째까지의 타일 채우기 다음에 1x2 타일을 채우는 1가지 경우와

N-2번째까지의 타일 채우기 다음에 2x1 타일을 2개 채우는 경우와 2x2 타일을 1개 채우는 경우 총 2가지를

합하는 것과 같다.

즉, 점화식은 dp[N] = dp[N-1] + (2 x dp[N-2]) 이다.

 

이를 코드로 구현하면 다음과 같다.

import java.io.*;

public class N11727 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N  = Integer.parseInt(br.readLine());

        int[] dp =  new int[Math.max(3, N + 1)];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 3;

        for (int i = 3; i <= N; i++) {
            dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;
        }

        bw.write(dp[N] + "\n");
        bw.flush();
    }
}

 

---

아직 초보라 많이 서툴고 틀린 부분이 있을 수 있습니다. 고수분들께서 조언해주실만한 사항이 있으면 감사히 받겠습니다.