[백준] 2003번 수들의 합2 JAVA (자바) 풀이

문제 2003 

 

N개의 수로 된 수열  =  A[1], A[2], …, A[N]

수열의 i ~ j번째 수까지의 합  =  A[i]+ … + A[j]  =  M이 되는 경우의 수 

 

 [입력]

 

 :  첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)

 :  다음 줄에는 A[1], A[2], …, A[N] (공백으로 분리 & 각각의 A[x]는 30,000을 넘지 않는 자연수)

 

 

 [출력]

 :  경우의 수 출력

 

 

 

 

 [참고]

 

기준숫자를 하나 잡고 합이 M될 때까지 for문 돌리기

 

• check(j) = 시작 숫자
  일단 j를 입력받으면 바로 이전 숫자들과 합부터 계산
  
  
  • 수열 합이 M이 되면 count하고 for문 break 
    
    
  • 수열 합이 M을 넘어서면 바로 for문 break

 

 [코드]

 

import java.io.*;
import java.util.*;
public class Main{
    static int arr[];
    static int N,M;
    static int count=0;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];
        
        
        st = new StringTokenizer(br.readLine());
        for(int i =0; i< N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        for(int j=0; j<N; j++){
            check(j);
        }
        
        System.out.println(count);
    }
    
    private static void check (int n){
        int sum = 0;
        
        for(int i=n;i<N;i++){
            sum += arr[i];
            if(sum==M){
                count++;
                break;
            }else if(sum>M)
                break;
        }
    }
}

 

 

 [해설]
     

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    st = new StringTokenizer(br.readLine());
        
 :  N = Integer.parseInt(st.nextToken());  N입력 (수열 개수)
    M = Integer.parseInt(st.nextToken());  M입력 (합)
    arr = new int[N];
        
        
 :  st = new StringTokenizer(br.readLine());
    for(int i =0; i< N; i++){  수열 입력
            arr[i] = Integer.parseInt(st.nextToken());
    }
        
 :  for(int j=0; j<N; j++){  N개의 시작점 
            check(j);
    }
        
 :  System.out.println(count);  출력
    

 :  private static void check (int n){
        int sum = 0;  합 초기화
        
        for(int i=n;i<N;i++){
            sum += arr[i];  수열 합치기
            if(sum==M){  합이 M이 되면 카운트
                count++;
                break;
            }else if(sum>M)  합이 M 넘어가면 바로 종료하고 시작점 바꾸기
                break;
        }
    }

    
 

 [시간 복잡도]

 

for문으로 j를 N만큼 입력받고 j마다 돌아가는 check메서드의 for문까지 총 두번의 for문을 거친다

시간복잡도는 O(N²) 이다

하지만 큰 입력값에는 비효율적이라 투 포인터(two pointers) 방식을 적용하면 효율적인 시간 복잡도 내에서 문제를 해결할 수 있다

 

이제 풀어보러 갈께요 :)

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2