글 읽기 - 질문입니다.. java시간초과

liasqui 4년 전 0

4
1 7
1 10
2 6
3 6

예시가 이렇게 주어진다면 2번행인 [1,10]이 같은 색인 [1,7] 보다 크니까 밑의 [2,6] , [3,6]과 비교 안하고 [1,7]의 sum값만 받으면 해결될줄 알았는데 안되네요..

고수님들 조언부탁드립니다..

import java.util.*;
import java.io.*;

public class Main {
	   public static void main(String[] args) throws IOException {
		   
	      BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	      int tc= Integer.parseInt(bf.readLine());
	      int sum[]=new int[tc];
	      String [][] data = new String[tc][2];
	      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	      for(int i=0; i<tc; i++) {
	    	  String[] tmp = bf.readLine().split(" ");
	    	  data[i][0] =tmp[0];
	    	  data[i][1] =tmp[1];
	      }
	      bf.close();
	      boolean b;
	   
	      for(int i=0; i<tc; i++) {
	
	    	  for(int j=0;j<tc; j++) {
	    		  b =data[i][0].equals(data[j][0]);
	    		  if(i>j && b==true && Integer.parseInt(data[i][1])>Integer.parseInt(data[j][1])) {
	    			  sum[i]=sum[j];
	    			  break;}
	    		  else if(b==false && Integer.parseInt(data[i][1])>Integer.parseInt(data[j][1])) 
	  	    		  sum[i]+=Integer.parseInt(data[j][1]);
	  	    	  }
		      System.out.println(sum[i]);

	    	  }

	   }
}

djm03178 4년 전 0

그렇게 '건너뛸 수 있게 만들어주는' 것이 우연히도 많다면 잘리겠지만, 그렇게 안 주어지는 경우에는 결국 O(N^2)으로 답이 없게 됩니다. 문제 풀이에서는 '웬만한 경우엔 되겠지'가 아니라 '어떠한 경우에도 되게' 만들어야 합니다.

liasqui 4년 전 0

댓글 감사합니다. 너무 좁게 생각하고있었네요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

질문입니다.. java시간초과

liasqui 4년 전 0

djm03178 4년 전 0

liasqui 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말