[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! 가 될꺼니 터진다.

 

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

돌려보자.

여기서 [16,21,24,24,21,16] 이란?

코끼리 수가 6마리 일때 첫 코끼리가 1일때, 2일때 ,3일때, 4일때 , 5일때 , 6일때 의 경우의 수이다.

 

근데.............

 

 

무슨 규칙이 있는거지???????????????????

 

아무리 봐도 안보인다;;;;

 

 

ㅈㄴ 고민하고 만져보려고

이번엔 작->크->작 만 만족하는 경우의 수를 구해보았다.

 

 

 

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

규칙............ 규칙이 뭔가 보인다.................

 

보이는가???

 

 

이걸 긁어와보자.

 

보이는가????????????

작크작 경우의수 를 안해봣으면 영영 이 규칙을 못찾을 뻔했다.

 

즉

d[i][j] = (d[i][j-1] - d[i-1][(i+1)-j]

           //왼쪽꺼     //위에서 뒤집은 번호

 

라는 것이다. 

 

그리고 작크작과 커작커의 경우의 수는 같을것이니 최종에서 *2 하면 떙이다!!!!

WOW!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 

 

그래서 코드를 이렇게 짜보았다.

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