글 읽기 - 시간초과 해결 좀요,...

deejay0825 6년 전 0

시간 초과 때문에....혹시 아시는 분..

import java.util.Scanner;

public class Main {
	
	
	public static void main(String[]args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      long s = sc.nextLong();
      int arr[]=  new int [n+1];
      long psum[]  = new long [n+1];
      int length = n+1;
      int count=0;
      for(int i =1;i<=n;i++) {
    	  arr[i] =sc.nextInt();
    	  psum[1] = arr[1];
    	  if(i>1) {
    	  psum[i] = psum[i-1]+arr[i];
    	  }
      }
      
      for(int i=1;i<=n;i++) {
    	  for(int j=i;j<=n;j++) {
    		
    		long sum = psum[j]-psum[i-1];
    		if(sum>=s&&length>=j-i+1) {
    			length = j-i+1;
    			count++;
    		}
    	  }
      }
      if(count>0) {
      System.out.println(length);}
      else {
    	  System.out.println("0");
      }
      
     }

}

djm03178 6년 전 0

이 코드는 O(N^2) 시간이 소요됩니다. 투 포인터를 써서 O(N) 시간에 해결해야 합니다. 모든 수가 자연수라는 것이 큰 힌트입니다.

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

문제

문제

출처

ICPC

시간초과 해결 좀요,...

deejay0825 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말