Guest User

Untitled

a guest
Feb 25th, 2018
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.91 KB | None | 0 0
  1. /*
  2. * 1806. 부분합
  3. * 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다.
  4. * 이 수열에서 연속된 수들의 부분합 중에 그 합이 S이상이 되는것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
  5. * [입력]
  6. * 첫째 줄에 N(10<N<100,000)과 S(0<S<100,000,000)가 주어진다.
  7. * 둘째 줄에는 수열이 주어진다.
  8. * 수열의 각 원소는 공백으로 구분되어 있으며, 10,000 이하의 자연수 이다.
  9. * [출력]
  10. * 첫째 줄에 구하고자 하는 최소의 길이를 출력한다.
  11. * 만일 그러한 합을 만드는 것이 불가능 하다면 0을 출력하면 된다.
  12. */
  13. import java.util.*;
  14. public class Main {
  15. static Scanner scan = new Scanner(System.in);
  16. static int n = scan.nextInt();
  17. static int s = scan.nextInt();
  18. static int[] arr = new int[n];
  19. // 최소 길이를 저장하기 위한 minlen 변수 초기화
  20. static int minlen = Integer.MAX_VALUE;
  21.  
  22. public static void main(String[] args) {
  23. // TODO Auto-generated method stub
  24. for(int i=0; i<arr.length; i++) {
  25. arr[i] = scan.nextInt();
  26. }
  27. int count = 0;
  28. for(int i=0; i<arr.length; i++) {
  29. int sum = arr[i];
  30. for(int j=i+1; j<arr.length; j++) {
  31. sum += arr[j];
  32. if(sum >= s) {
  33. count = Math.abs(j-i); // 길이를 저장해야 하기 때문에 i와 j를 이용한 자리 값으로 count 저장
  34. if(minlen > count) {
  35. minlen = count;
  36. break; // sum >= s 조건을 만족하면 break하여 다음 i값으로 비교 시작
  37. }
  38. count = 0; // 조건을 만족하고 초기화
  39. sum = 0; // 조건을 만족하고 초기화
  40. }
  41. }
  42. }
  43. if(n>=s) {
  44. System.out.println(minlen);
  45. } else if(minlen == Integer.MAX_VALUE) { // 만족못하는 경우 0으로 출력
  46. System.out.println(0);
  47. } else { // n<s 인 경우 arr배열이 0부터 시작하기 때문에 minlen에 1을 더한 값을 출력
  48. System.out.println(minlen+1);
  49. }
  50. }
  51. }
Add Comment
Please, Sign In to add comment