[DP] 규칙찾기 + pro_코끼리
일단 문제부터 보자....
제목 : 코끼리 서커스
□ 문제
코끼리의 코 길이는 모두 다르다
한줄 행으로 줄을 세운다
□ 요건
아래 조건이 만족하는 경우의 수를구하라
커작커(크고 작고 크고순서로)
A1 < A2 > A3
작커작(작고 크고 작고순서로)
A1 > A2 < A3
□ 범위
마리(N) : 2 ~ 300 마리
코 길이 : 1~ 300
□ 출력
10,0000,0007로 나눈 나머지 출력
적합한 경우의 수 출력
□ 입력
3
3
4
300
(입력케이스가 3개이고 각 케이스는 3마리, 4마리, 300마리 이다.)
□ 결과
#1 4
#2 10
#3 692892583
----------------------------
□ 풀이
3마리인 경우(경의수 6가지)
조건 만족 4개
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
??????????????????????????????????????????
뭔가 ㅈㄴ DP 같은데 처음 보고 ?????????????????????? 했었다.
그래도 풀 수 있으니깐 던져줬겠지 하고 일일히 해보기로 했다.
손은 힘드니깐 프로그램을 짜자...
밑에 프로그램은
코끼리 코가 2~ 7개일때
첫 수가 1일때 ~ 코개 일 때 를 나열한 것이다.
당연히 브루트 포스하게 한거니 300으로 하면 300! 가 될꺼니 터진다.
|
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
import java.util.*;
import java.io.*;
import java.math.*;
public class D210420_pro190119_코끼리서커스 {
static int[] cnt;
public static void main(String[] args) throws IOException {
//System.setIn(new FileInputStream("input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// n을 넣으면
//int n = Integer.parseInt(br.readLine());
for(int z = 2 ; z <= 7 ; z++) {
int[] arr = new int[z];
for(int i = 0 ; i < z ; i++)
arr[i] = i+1;
cnt = new int[z+1];
while(true) {
go(arr);
if(!nextPermutation(arr)) // 브루트 포스 + next_permutation
break;
}
System.out.print(Arrays.toString(cnt) + " ");
int sum = 0;
for(int i = 1 ; i <= z ; i++)
sum += cnt[i];
System.out.println(sum);
}
}
/*
배열 arr에 대해서 상승 -> 하락 -> 상승 or 하락 -> 상승 -> 하락
일 경우에 arr[0] 그니깐 시작 수 에대가 cnt를 ++ 한다.
*/
static void go(int[] arr) {
int su = arr[0];
boolean flag;
// true는 상승장 false는 하락장
if(arr[0] < arr[1])
flag = true;
else
flag = false;
for(int i = 1 ; i < arr.length-1 ; i++) {
if(arr[i] < arr[i+1]) {
if(flag == true)
return;
else
flag = true;
}
else {
if(flag == true)
flag = false;
else
return;
}
}
cnt[su]++;
}
static boolean nextPermutation(int[] arr){
int i = arr.length-1;
while(i>0 && arr[i-1]>=arr[i]) --i;
if(i==0) return false;
int j = arr.length - 1;
while(arr[i-1]>=arr[j]) --j;
int temp = arr[i-1];
arr[i-1] = arr[j];
arr[j] = temp;
int k = arr.length-1;
while(i<k){
temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
i++; k--;
}
return true;
}
}
|
cs |
돌려보자.
여기서 [16,21,24,24,21,16] 이란?
코끼리 수가 6마리 일때 첫 코끼리가 1일때, 2일때 ,3일때, 4일때 , 5일때 , 6일때 의 경우의 수이다.
근데.............
무슨 규칙이 있는거지???????????????????
아무리 봐도 안보인다;;;;
ㅈㄴ 고민하고 만져보려고
이번엔 작->크->작 만 만족하는 경우의 수를 구해보았다.
|
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
import java.util.*;
import java.io.*;
import java.math.*;
public class D210420_pro190119_코끼리서커스 {
static int[] cnt;
public static void main(String[] args) throws IOException {
//System.setIn(new FileInputStream("input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// n을 넣으면
//int n = Integer.parseInt(br.readLine());
for(int z = 2 ; z <= 7 ; z++) {
int[] arr = new int[z];
for(int i = 0 ; i < z ; i++)
arr[i] = i+1;
cnt = new int[z+1];
while(true) {
go(arr);
if(!nextPermutation(arr)) // 브루트 포스 + next_permutation
break;
}
System.out.print(Arrays.toString(cnt) + " ");
int sum = 0;
for(int i = 1 ; i <= z ; i++)
sum += cnt[i];
System.out.println(sum);
}
}
static void go(int[] arr) { // 작크작
int su = arr[0];
boolean flag = false;
for(int i = 0 ; i < arr.length-1 ; i++) {
if(arr[i] < arr[i+1]) {
if(flag == true)
return;
else
flag = true;
}
else {
if(flag == true)
flag = false;
else
return;
}
}
cnt[su]++;
}
static boolean nextPermutation(int[] arr){
int i = arr.length-1;
while(i>0 && arr[i-1]>=arr[i]) --i;
if(i==0) return false;
int j = arr.length - 1;
while(arr[i-1]>=arr[j]) --j;
int temp = arr[i-1];
arr[i-1] = arr[j];
arr[j] = temp;
int k = arr.length-1;
while(i<k){
temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
i++; k--;
}
return true;
}
}
|
cs |
규칙............ 규칙이 뭔가 보인다.................
보이는가???
이걸 긁어와보자.
보이는가????????????
작크작 경우의수 를 안해봣으면 영영 이 규칙을 못찾을 뻔했다.
즉
d[i][j] = (d[i][j-1] - d[i-1][(i+1)-j]
//왼쪽꺼 //위에서 뒤집은 번호
라는 것이다.
그리고 작크작과 커작커의 경우의 수는 같을것이니 최종에서 *2 하면 떙이다!!!!
WOW!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
그래서 코드를 이렇게 짜보았다.
|
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
40
41
42
43
44
45
|
import java.util.*;
import java.io.*;
import java.math.*;
public class D210420_pro190119_코끼리서커스_2 {
static final int INF = 1000000007;
public static void main(String[] args) throws IOException {
//System.setIn(new FileInputStream("input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int tc = Integer.parseInt(br.readLine());
for(int z = 1 ; z <= tc ; z++) {
int n = Integer.parseInt(br.readLine());
int d[][] = new int[n+1][n+1];
d[1][1] = 1;
d[2][1] = 1;
d[2][2] = 0;
int sum = 1;
for(int i = 3 ; i <= n ; i++) {
d[i][1] = sum;
sum = d[i][1];
for(int j = 2 ; j <= i ; j++) {
d[i][j] = (d[i][j-1] - d[i-1][(i+1)-j]+INF)%INF;
sum = (sum+ d[i][j])%INF;
}
}
/*
for(int i = 1 ; i <= n ; i++) {
for(int j = 1 ; j <= i ; j++)
System.out.print(d[i][j] + " ");
System.out.println();
}*/
System.out.println("#"+z+" "+(sum*2)%INF);
}
}
}
|
cs |