[Beakjoon] 11726 2xn 타일링 - JAVA

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

2x5 타일 채우기 예시

---

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

---

출력

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

---

예제 입력 1 

2

예제 출력 1 

2

예제 입력 2 

9

예제 출력 2 

55

---

📝 제출 답안

✔️ 첫 번째 제출

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Long[] dp = new Long[1001];
        dp[0] = 1L;
        dp[1] = 1L;

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

        int n = Integer.parseInt(br.readLine());
        bw.write(String.valueOf(dp[n]));
        bw.flush();
    }
}

 

✔️ 두 번째 제출

import java.io.*;

public class Main {
    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());
        Long[] dp = new Long[n+1];
        dp[0] = 1L;
        dp[1] = 1L;

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

        bw.write(String.valueOf(dp[n]));
        bw.flush();
    }
}

 

우선 맨 처음 답을 제출할 때에는 10,007을 출력하기 직전에 dp[n]%10007로 계산해서 오답 처리가 되었다.

너무 큰수를 저장하지 않도록 점화식 부분에서 10,007로 나눈 나머지를 저장할 수 있게 로직을 수정해주었다.

(사실 이래서 int[] 형 배열이 아닌 Long[] 타입의 배열로 풀게되었다..ㅎ먼저 제대로 나누고 나머지만 저장했으면 int[] 배열을 써도 충분했음.)

 

입출력 처리

BufferedReader와 BufferedWriter를 사용해 입출력 처리 속도를 향상시켰다.

n값을 입력받아 dp 배열을 초기화할 것이다.

 

DP 배열

dp 알고리즘으로 피보나치 수를 저장한다.

첫 번째 풀이에서는 이 문제에서 주어진 최대값 1000을 고려해 dp[1001]로 초기화 했었다.

 

하지만 제출 후 생각해보니 굳이 1000번까지 저장해두는 것보다 입력 받은 수만큼만 dp[n+1]로 배열에 값을 저장해두었다가 사용하는 것이 좀 더 효율적일 것이라고 생각해서 두 번째 풀이로 풀게 되었다. 시간이 좀 더 빨라질 줄 알았지만 시간은 그대로 였고, 사용 메모리는 조금 줄어들었다.

 

dp[0] = dp[1] = 1로 초기값을 설정해주고, 이후의 값은 점화식에 의해 값을 저장한다.

해당 문제에서의 점화식은 dp[n] = dp[n-1] + dp[n-2] 이다.

 

규칙을 살펴보자면

n=1 이면 2*1 크기의 직사각형을 만들 수 있는 방법이 1가지이고,

n=2 이면 2*2 크기의 직사각형을 만들 수 있는 방법이 2가지,

n=3 일 때는 방법이 3가지,

n=4 일 때는 방법이 5가지,

n=5 일 때는 방법이 8가지 ...

이처럼 차례대로 써보면 n번째 방법의 수는 n-1과 n-2번째의 방법 수를 합한 것과 같다.

그래서 점화식인 dp[n] = dp[n-1] + dp[n-2] 와 같이 나온 것이다.

 

단 문제에서 구하고자 하는 답은 n번째 방법의 수를 10007로 나눈 나머지를 묻고 있기 때문에

배열에 저장하기 전에 10007을 나눈 나머지를 구해준 뒤 저장한다. 이렇게 하면 너무 큰 값을 처리하지 않도록 제한할 수 있다는 장점이 있다.

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

 

마지막으로 출력은 n번째 배열의 값을 문자열로 바꾸어 출력한다.

이는 bw.write 메서드가 문자열만을 처리할 수 있기 때문이다.

 

제출 현황