https://www.acmicpc.net/problem/11727
방법 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
|
연산은 한 라인에서 끝내도록 하였더니 해결되었다.
'Algorithm > BOJ' 카테고리의 다른 글
[BOJ]11052번: 카드 구매하기(java, c++) (0) | 2019.10.14 |
---|---|
[BOJ]9095번: 1, 2, 3 더하기(java, c++) (0) | 2019.10.14 |
[BOJ]11726번: 2×n 타일링(java, c++) (0) | 2019.10.14 |
[BOJ]1463번: 1로 만들기(java, c++) (0) | 2019.10.14 |
[BOJ]11653번: 소인수분해(java, c++) (0) | 2019.09.25 |
댓글