[백준] 2×n 타일링 - 자바

 

비교적 쉽게 풀은 ! 

그려보다 보면 눈에 잘 보인다!

 

i = 2이기 위해

i = 0에서 + 2를 해야하므로 두개를 가로로 쌓고 (세로로 쌓으면 겹치는 방법이 존재)

i = 1에서 + 1을 해야하므로 세로로 하나를 쌓는다.

 

i = 3이기 위해

i = 1에서 + 2를 해야하므로 두개씩 가로로 쌓고 (세로로 쌓으면 겹치는 방법이 존재)

i = 2에서 + 1을 해야하므로 세로로 하나씩 쌓는다.

 

i = 4이기 위해

i = 2에서 + 2를 해야하므로 두개씩 가로로 쌓고 (세로로 쌓으면 겹치는 방법이 존재)

i = 3에서 + 1을 해야하므로 세로로 하나씩 쌓는다.

 

i = 5이기 위해

i = 3에서 + 2를 해야하므로 두개씩 가로로 쌓고 (세로로 쌓으면 겹치는 방법이 존재)

i = 4에서 + 1을 해야하므로 세로로 하나씩 쌓는다.

따라서 !

i ( > 1)에 대해서 i - 1와 i - 2의 방법의 수를 더하면 i의 방법의 수가 된다.

즉 점화식은 dp[ n ] = ( dp[ n - 1 ] + dp[ n - 2 ] )

 

주어진 n의 범위가 1 ≤ n ≤ 1,000 이므로 배열의 0번째, 1번째를 담아 2번째 배열부터 계산하도록 했다.

int[] dp = new int[n+1]; // new int[2];
dp[0] = 1;
dp[1] = 1;

 

배열의 1번째, 2번째를 담아 3번째 배열부터 계산해도 괜찮을 것 같은데,

만약 n = 1일 때 배열을 n+1만큼 선언 후

배열의 1번째, 2번째를 담으면 인덱스 오류가 날 것 같아서 위의 방법을 선택했다. (이러한 예제를 넣었는지는 테스트해보지는 않음)

int[] dp = new int[n+1]; // new int[2];
dp[1] = 1;
dp[2] = 2;	// 인덱스 오류

 

출력

그리고 제일 중요한 부분은 이 부분!

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

처음에 이 부분을 확인하지 못 하고 제출하여 실패가 되었다 ㅜㅜ

숫자가 계속 더해져 커지면 int 형 범위를 초과하여 Overflow가 발생하여 잘못된 값이 저장될 수 있다. 

따라서 계속 숫자를 더하고 저장하여 마지막에 그 값을 불러와 10,007로 나눈 값으로 출력하는 것이 아닌

저장할 때마다 10,007로 나누어 값을 저장한 후 출력해야한다.

 

import java.io.*;
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[N+1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= N; i++) dp[i] = (dp[i-1] + dp[i-2]) % 10007;
        System.out.println(dp[N]); // 출력 부분에서 dp[N] % 10007하지 않고 for문 안에서 계산하여 저장
    }
}