경우의 수를 구하는 DP로 생각을 했다.
테이블을 [N][3] 크기로 만들고
[N][0] 이번 라인에 없는 경우
[N][1] 이번 라인은 왼쪽
[N][2] 이번 라인은 오른쪽
으로 생각 하고 문제를 품.
한방에 해결.
|
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
|
public class Main {
static int[][] caseArr;
static int na = 9901;
static int result;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
caseArr = new int[N][3];
for (int i = 0; i < caseArr[0].length; i++) {
caseArr[0][i] = 1;
}
for (int i = 1; i < caseArr.length; i++) {
for (int j = 0; j < caseArr[i].length; j++) {
// 하나도 없는 경우
caseArr[i][0] = (caseArr[i - 1][0] + caseArr[i - 1][1] + caseArr[i - 1][2]) % na;
// 왼쪽에 있는 경우
caseArr[i][1] = (caseArr[i - 1][0] + caseArr[i - 1][2]) % na;
// 오른쪽에 있는 경우
caseArr[i][2] = (caseArr[i - 1][0] + caseArr[i - 1][1]) % na;
}
}
result = ((caseArr[N - 1][0] + caseArr[N - 1][1] + caseArr[N - 1][2]) % na);
System.out.println(result);
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
하고 나서 보니 답에 규칙이 또 있는거 같아 줄여보았다.
|
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
|
public class Main {
static int[] caseArr;
static int na = 9901;
static int result;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
caseArr = new int[N + 1];
caseArr[0] = 1;
caseArr[1] = 3;
for (int i = 2; i < caseArr.length; i++) {
caseArr[i] = (caseArr[i-2] + (caseArr[i-1]*2)) % na;
}
System.out.println(caseArr[N]);
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
메모리와 시간이 줄었음.
역시 한방에 해결
'it > 알고리즘' 카테고리의 다른 글
| 백준 10026 - 적록색약 (0) | 2019.09.01 |
|---|---|
| 백준 11057 - 오르막 수 (0) | 2019.09.01 |
| 백준 4485 녹색 옷 입은 애가 젤다 (0) | 2018.11.24 |
| 스택을 이용한 문제 (0) | 2015.01.06 |
| 힙을 이용한 트리 (0) | 2015.01.06 |
