NUMB3RS문제푸는중입니다.. 시간초과가 뜨네요... 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 cache를 사용하시나요? 9년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
clearpal6
시간초과가 뜨는데 어떤식으로 접근하는게 좋을까요??
public class Main {
}
9년 전