[백준 11726번] 2xn 타일링

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

11726번: 2×n 타일링

1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

2행 n열의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 문제이다.

2xn의 직사각형이기 때문에 = 이나 || 둘중 한가지 모양으로 직사각형을 채워나가 경우의 수를 구할 수 있을것으로 보인다.

n은 1<=n<=100 인 자연수이다.

 

 

2. 나의 방식대로 문제를 재정의 하자.

dp[] 배열로 memorization 하여 값을 저장한다.

반복문, 재귀함수를 통해 해결할 수 있다.

2x1 타일 : | 형태 1개

2x2 타일 :  || = 형태 2개

2x3 타일 : 2x1타일에 =을 이어붙힌 형태, 2x2타일에 |을 이어붙힌 형태 --> 1 + 2 = 3

2x4 타일 : 2x2타일에 =을 이어붙힌 형태, 2x3타일에 |을 이어붙힌 형태 --> 2 + 3 = 5

2x5 타일 : 2x3타일에 =을 이어붙힌 형태, 2x4타일에 |을 이어붙힌 형태 --> 3 + 5 = 8

...

dp[n] = dp[n-1] + dp[n-2]임을 이용해 문제를 해결한다.

 

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

dp[] 배열로 memorization 하여 값을 저장한다.

반복문, 재귀함수를 통해 해결할 수 있다.

 

 

4. 어떻게 계산할 것인가?

1) 입력

열의 크기인 n을 입력받음

 

2) 시간 복잡도 계산

반복문을 통해 해결할 경우 O(n)이 걸린다.

 

5. 주의할 점은 무엇인가?

출력값 조건에 소수인 10007을 나눈 나머지를 출력하도록 되어있다.

 

6. 풀이 과정

dp[n] = dp[n-1] + dp[n-2]임을 이용해 문제를 해결한다.

 

buttom-up

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());
        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;
        }

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

        bw.flush();
        br.close();
        bw.close();
    }
    
    
}

 

top-down

import java.io.*;

public class Main {
    static int[] dp;
    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());
        dp = new int[N + 1];
        dp[0] = 1;
        dp[1] = 1;

        dpFunc(N);

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

        bw.flush();
        br.close();
        bw.close();
    }
    
    static Integer dpFunc(int n) {
        if (n == 1) {
            return dp[n];
        }

        if (dp[n] != 0) {
            return dp[n];
        }
        
        dp[n] = (dpFunc(n-1) + dpFunc(n-2))%10007;
        return dp[n];

    }
    
    
}

 

7. 개선점

처음 문제를 풀 때 문제 식 유도는 잘 됐지만 초기값을 설정할 때 0,1,2에 값을 미리 넣어놓아서 N=1인 경우 배열의 크기는 2인데 없는 인덱스인 dp[2]를 참조하는 문제가 발생했다.