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

아이디어

이번 문제는 DP이다.

이번에는 다행이 보자마자 점화식이 바로 보였다.

저번에 푼 문제와 마찬가지로 마지막에 오는 경우에 따라 두가지로 나뉜다.

예를 들어, n이 3일 때 마지막 한 열에 세로로 직사각형을 둘 수 있고

마지막 한 열과 그 앞 열을 써서 가로로 2개를 둘 수 있다.

그 경우 경우의 수는 n이 1일 때와 n이 2일 때의 경우의 수를 합한 것과 같다.

즉, 점화식은 dp[n] = dp[n-1] + dp[n-2]이다.

이 점화식은 n이 3부터 유효하기 때문에, n은 2까지는 미리 선언해둔다.

 

그런데 점화식은 맞게 썼는데, 자꾸 오답이 났다. int로 둬서 오버플로우가 나는 것인가 싶어서 long으로 바꿨는데도 그랬다.

그런데 보니까 long으로 둬도 오버플로우가 나는 숫자더라.

그래서 점화식에서 합하는 과정에서 dp[n-1]과 dp[n-2]에서 미리 10007로 나눠주었다.

그 후 두 나머지의 합이 10007을 넘는 경우를 고려해 결과를 구할 때 한번 더 dp[n]을 10007로 나누었다.

 

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

import java.io.*;

public class N11726 {
    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] = 2;

        for (int i = 3; i <= N; i++) {
            dp[i] = dp[i - 1] % 10007 + dp[i - 2] % 10007;
        }
        int result = dp[N] % 10007;
        bw.write(result + "");
        bw.flush();
    }
}

 

---

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