Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * 1806. 부분합
- * 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다.
- * 이 수열에서 연속된 수들의 부분합 중에 그 합이 S이상이 되는것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
- * [입력]
- * 첫째 줄에 N(10<N<100,000)과 S(0<S<100,000,000)가 주어진다.
- * 둘째 줄에는 수열이 주어진다.
- * 수열의 각 원소는 공백으로 구분되어 있으며, 10,000 이하의 자연수 이다.
- * [출력]
- * 첫째 줄에 구하고자 하는 최소의 길이를 출력한다.
- * 만일 그러한 합을 만드는 것이 불가능 하다면 0을 출력하면 된다.
- */
- import java.util.*;
- public class Main {
- static Scanner scan = new Scanner(System.in);
- static int n = scan.nextInt();
- static int s = scan.nextInt();
- static int[] arr = new int[n];
- // 최소 길이를 저장하기 위한 minlen 변수 초기화
- static int minlen = Integer.MAX_VALUE;
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- for(int i=0; i<arr.length; i++) {
- arr[i] = scan.nextInt();
- }
- int count = 0;
- for(int i=0; i<arr.length; i++) {
- int sum = arr[i];
- for(int j=i+1; j<arr.length; j++) {
- sum += arr[j];
- if(sum >= s) {
- count = Math.abs(j-i); // 길이를 저장해야 하기 때문에 i와 j를 이용한 자리 값으로 count 저장
- if(minlen > count) {
- minlen = count;
- break; // sum >= s 조건을 만족하면 break하여 다음 i값으로 비교 시작
- }
- count = 0; // 조건을 만족하고 초기화
- sum = 0; // 조건을 만족하고 초기화
- }
- }
- }
- if(n>=s) {
- System.out.println(minlen);
- } else if(minlen == Integer.MAX_VALUE) { // 만족못하는 경우 0으로 출력
- System.out.println(0);
- } else { // n<s 인 경우 arr배열이 0부터 시작하기 때문에 minlen에 1을 더한 값을 출력
- System.out.println(minlen+1);
- }
- }
- }
Add Comment
Please, Sign In to add comment