NUMB3RS문제푸는중입니다.. 시간초과가 뜨네요...

  • clearpal6
    clearpal6

    시간초과가 뜨는데 어떤식으로 접근하는게 좋을까요??

    public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
    
        Scanner scan = new Scanner(System.in);
        GraphNode head[];
    
        int TestCase = 0;
        int town[][];
        int N; // 마을의수;
        int D; // 지난 일수
        int P; // 감옥 마을
        int pCount; // 확률을 구할 마을의 갯수
        float prob[];
        int p[];
    
        TestCase = scan.nextInt();
    
    
        while (TestCase-- > 0) {
            N = scan.nextInt();
            D = scan.nextInt();
            P = scan.nextInt();
            head = new GraphNode[N];
            town = new int[N][N];
    
            float cache[][]=new float[N][D];
    
            if(N>=2 && N<=50 && D>=1 && D<=100){
    
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    town[i][j] = scan.nextInt();
                }
            }
    
            pCount = scan.nextInt();
            p= new int[pCount]; // 확률을 구할 마을
            prob=new float[pCount];
            for (int i = 0; i < pCount; i++) {
                p[i] = scan.nextInt();
            }
    
            insertEdge(head, town, N);
    
            init(head, N); // 사이즈 정의하는 함수.
    
            for (int i = 0; i < pCount; i++) {
                prob[i] = 1;
                System.out.println(probability(head, p[i], D, P, prob[i],cache));
            }
            }
        }
    }
    
    private static float probability(GraphNode[] head, int objective,
            int day, int prison, float prob,float cache[][]) {
        // TODO Auto-generated method stub
    
        float ans = 0;
        if (day == 0 && prison == objective) {
            return prob;
        } else if (day == 0) {
            return 0;
        } else {
            GraphNode gNode = new GraphNode();
            gNode = head[prison];
            prob = prob * (float) 1 / gNode.size;
            while (gNode != null) {
                ans += probability(head, objective, day - 1, gNode.vertex,prob,cache);
                gNode = gNode.link;
            }
        }
        return ans;
    }
    
    private static void init(GraphNode head[], int N) {
        // TODO Auto-generated method stub
        GraphNode gNode = new GraphNode();
        for (int i = 0; i < N; i++) {
            gNode = head[i];
            while (gNode != null) {
                head[i].size++;
                gNode = gNode.link;
            }
        }
    }
    
    public static void insertEdge(GraphNode[] head, int town[][], int N) {
    
        for (int i = 0; i < N; i++) {
    
            for (int j = 0; j < N; j++) {
                if (town[i][j] == 1) {
                    GraphNode gNode = new GraphNode();
                    gNode.vertex = j;
                    gNode.link = head[i];
                    head[i] = gNode;
                }
    
            }
        }
    }
    
    static class GraphNode {
        int vertex;
        int size = 0;
        GraphNode link;
    }

    }


    9년 전
1개의 댓글이 있습니다.
  • JongMan
    JongMan

    cache를 사용하시나요?


    9년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.