본문 바로가기
Algorithm/BOJ

[BOJ]11727번: 2×n 타일링 2(java, c++)

by HBGB 2019. 10. 14.

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

 

11727번: 2×n 타일링 2

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

www.acmicpc.net

 

방법 1: Top-down

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.io.*;
 
public class Main {
    public static int[] arrCount;
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
            int num = Integer.parseInt(br.readLine());
            arrCount = new int[num + 1]; 
            
            System.out.println(calculate(num));
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    
    public static int calculate(int num) {
 
        if (num == 1) {
            return 1;
        } else if (num == 2) {
            return 3;
        } else if (arrCount[num] > 0) {
            return arrCount[num];
        }
        
        arrCount[num] = (calculate(num - 1+ 2 * calculate(num - 2)) % 10007;
        
        return arrCount[num];
    }
}
Colored by Color Scripter

 

c++소스

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
 
using namespace std;
 
const int DIV = 10007;
const int MAX = 1000;
int D[MAX + 1];
 
// 점화식 : D[n] = D[n - 1] + D[n - 2] * 2;
int make_tile(int n)
{
    if (D[n] > 0)
    {
        return D[n];
    }
    // 종료 조건
    if (n <= 1)
    {
        return D[n] = 1;
    }
 
    return D[n] = (make_tile(n - 1+ make_tile(n - 2* 2) % DIV;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    cin >> n;
 
    make_tile(n);
 
    cout << D[n];
 
    return 0;
}
Colored by Color Scripter
 

방법 2: Bottom-up

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.io.*;
 
public class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
            int num = Integer.parseInt(br.readLine());
            int[] arrCount = new int[1001]; 
            
            arrCount[1= 1;
            arrCount[2= 3;
            
            for (int i = 3; i < arrCount.length; i++) {
                arrCount[i] = (arrCount[i - 1+ 2 * arrCount[i - 2] ) % 10007;
            }
            
            System.out.println(arrCount[num]);
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    } 
}
Colored by Color Scripter

 

c++소스

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    cin >> n;
 
    const int DIV = 10007;
    const int MAX = 1000;
    int D[MAX + 1];
 
    D[0= 1;
    D[1= 1;
 
    // 점화식 : D[n] = D[n - 1] + D[n - 2] * 2;
    for (int i = 2; i <= n; i++)
    {
        D[i] = (D[i - 1+ D[i - 2* 2) % DIV;
    }
 
    cout << D[n];
 
    return 0;
}
Colored by Color Scripter

 

이 문제에선 탑다운이 바텀 업보다 아주 근소하게 더 빨랐다.

 

 

TIP1

2 * n 타일링 문제보다 사각형을 채우는 방법 한가지수가 더 늘어났다.

풀이 방식은 똑같다.

늘어나는 가로 길이가 어디에서부터 증가하였는지만 살피면 된다. 

 

 

TIP2

1
2
3
arrCount[num] = calculate(num - 1+ 2 * calculate(num - 2);
 
return arrCount[num] % 10007;
 
Colored by Color Scripter

탑다운 방식으로 풀 때, 위와 같이 코딩했더니 시간 초과 오류가 났다. 

 

1
2
3
arrCount[num] = (calculate(num - 1+ 2 * calculate(num - 2)) % 10007;
        
return arrCount[num];
 
Colored by Color Scripter

연산은 한 라인에서 끝내도록 하였더니 해결되었다. 

 

댓글