#쉽게 푸는 알고리즘 #6 수들의 합 4 백준 2015번

이번에 설명할 알고리즘은 백준 2015번 수들의 합4 를 설명해 보겠습니다.

문제는 A[N] 개의 정수가 저장된 배열이 있는데 여기서 1<=i<=j<N 인 정수 i와 j에 대해서 A[i] 부터 A[j] 까지의 합이 사용자가 원하는 숫자로 된것이 몇개 있냐 라는 문제입니다.

예제를 보면 4개의 배열로 설정하고 원하는 숫자의 합은 0 이라 할때 배열들이 2,-2,2-2 일때 경우의 수는

2 + (-2) = 0

2 + (-2) + 2 (-2) = 0

-2 + 2 = 0

2 + (-2) = 0

이렇게 해서 값은 4개가 됩니다.

그럼 다른 예제로 보면

배열은 6개 원하는 숫자의 합은 2일때 배열들은 2, -3 , 4 , 5 , -6 , -2 일때 경우의 수는

2 = 2

2 + (-3) + 4 + 5 + (-6) = 2

이렇게 해서 값은 2개가 됩니다.

캡처 사진으로는

그럼 소스를 보여드리겠습니다.

package blog;

import java.util.Scanner;

public class blogClass {
 static int Arr[];
 static int Sum = 0;
 static int Count =0;
 public static void main(String[] args) {
  System.out.println("http://jsieun73.tistory.com/");
  Scanner scan = new Scanner(System.in);
  System.out.println("몇개의 수와 원하는 합을 말하시오 ");
  int _Size = scan.nextInt();
  Sum = scan.nextInt();
  Arr = new int[_Size];
  System.out.println("수들을 입력하시오 ");
  for(int i=0; i< _Size; i++)
  {
   Arr[i] = scan.nextInt();
  }
  partSum(_Size);
  System.out.println("답은 : " + Count);
  
 }
 static void partSum(int _Size){
  int trySum = 0;
  for(int i=0; i<_Size; i++)
  {
   trySum = 0;
   for(int j=i; j<_Size; j++)
   {
    trySum += Arr[j];
    if(Sum == trySum)
    {
     Count++;
    }
   }
  }
 }
}

소스 해석을 하도록 하겠습니다.

1. 메인함수 여긴 값들과 배열의 사이즈 값을 설정하는 것이라서 그렇게 중요하진 않습니다.

2.partSum 메소드 중요도 ☆☆☆★★

생각 보다 간단합니다. 반복문 2개를 두고 trySum 이라고하는 변수에 배열들이 1씩 증가할때마다 그에 해당되는

값들을 누적해서 합합니다. 그러다가 자신이 원하는 합이 나왔을때 카운팅을 들어가도록 설정합니다.

그리고 반복문을 설명하자면,

이렇게 구성이 됩니다. 문제 조건에서 i와 j의 범위가 1<=i<=j<=N 이니까 반복문을 저렇게 설정하면 되겠습니다.

이상 포스팅을 마치도록 하겠습니다.