[백준] code.plus(브루트포스 - 기타,JAVA)2003번, 수들의 합 2

문제 링크

2003번: 수들의 합 2

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

이 문제에 핵심은

1. 입력된 수열에서 범위의 합이 M가 같은 개수를 결과로 출력해야 한다.

2. 수열의 값은 1~N개로 나누어진다.

 

저는 두 포인터 알고리즘을 이용하여 구현하였습니다.

 

두 포인터 알고리즘은 수열의 범위에 시작과 끝을 가리키는 변수를 저장하여 포인터를 변경시키는 알고리즘입니다.

 

두개의 포인터 변경 규칙

범위의 합이 목표의 값보다 크면 : Start + 1범위의 합이 목표의 값보다 작거나 같으면 : End + 1

 

예제입력1에서 적용시키면

두 포인터 변수 : Start, End

Start : 1End : 1범위의 합 : 1

1	1	1	1
Start, End

범위의 값이 목표(2)보다 작기 때문에 범위를 늘려야 합니다.

 

Start : 1

End : 2

범위의 합 : 2

1	1	1	1
Start	End

범위의 값이 목표(2)보다 같아서 범위를 늘리고 결과 + 1을 진행한다.

 

Start : 1

End : 3

범위의 합 : 3

1	1	1	1
Start		End

범위의 값이 목표(2)보다 커서 범위를 줄인다.

 

Start : 2

End : 3

범위의 합 : 2

1	1	1	1
	Start	End

범위의 값이 목표(2)보다 같아서 범위를 늘리고 결과 + 1을 진행한다.

 

Start : 2

End : 4

범위의 합 : 3

1	1	1	1
	Start		End

범위의 값이 목표(2)보다 커서 범위를 줄인다.

 

Start : 3

End : 4

범위의 합 : 2

1	1	1	1
		Start	End

범위의 값이 목표(2)보다 같아서 범위를 늘리고 결과 + 1을 진행한다.

 

Start : 4

End : 4

범위의 합 : 1

1	1	1	1
			Start, End

범위의 값이 목표(2)보다 작기 때문에 범위를 늘려야 합니다.

여기서 End값을 더하면 수열의 범위에 벗어나기 때문에 탐색이 종료됩니다.

 

결과적으로 목표(2)가 나온 경우는 3번으로 3이 결과로 출력됩니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 수열에 대한 정보를 저장하였습니다.
• 두 포인터를 이용하여 수열의 범위합이 목표 값이 되는 횟수를 구하는 cal함수를 실행하였습니다.
• cal함수로 얻은 횟수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal함수는 두 포인터 알고리즘을 이용하여 수열의 범위합이 목표값을 같는 횟수를 구합니다.

 

import java.io.*;
import java.util.*;

public class Main{
	static int N,M;
	static int[] A;	//수열 정보 저장 배열
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		A = new int[N];
		st = new StringTokenizer(br.readLine()," ");
        	//입력되는 수열의 값 저장
		for(int i=0;i<N;i++)
			A[i] = Integer.parseInt(st.nextToken());
        	//두 개의 포인터 선언
		int start = 0;
		int end = 0;
		int result = cal(start, end, M);	//두 포인터 알고리즘 시작
		bw.write(result + "\n");		//목표 값 되는 횟수 BufferedWriter 저장
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//두 포인터로 범위의 합이 목표 값이 되는 횟수 구하는 함수
	public static int cal(int start, int end, int goal) {
		int count = 0;		// 횟수
		int value = A[start];	//시작 값
		while(end<N) {		//두 포인터로 탐색 시작
			if(value>goal) {	//범위 값이 클 경우
				value-= A[start];	//범위 감소로 범위 값 감소
				start++;
			}else {		//범위 값이 작거나 같은 경우
				if(value==goal)		//목표와 같을 때 횟수 + 1
					count++;
				end++;
				if(end>N-1)
					break;
				value += A[end];	//범위 증가로 범위 값 증가
			}
		}
		return count;	//횟수 반환
	}
}