[백준 스터디 10주차] 1806번 부분합 골드4 - 자바(JAVA) / 투 포인터

📑 문제

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

1806번: 부분합

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

 

 

 

 

 

 

 

✒️ 풀이

 투 포인터를 써보자 해서 고른 문제였다. 어딘가의 코테에서도 아래와 같은 코드로 비슷하게 풀었던 기억이 있다.

🔥 이 문제의 경우 코드 유형을 외워두면 두고두고 잘 쓸 수 있으니 외워두자! 🔥

 

 ✔️ 맨 처음 위치에 투 포인터를 둔다.

 ✔️ 현재 SUM 값이 목표보다 적으면, 오른쪽 포인터를 한 칸 증가시키고 그 값을 더해준다. 

 ✔️ 현재 SUM 값이 목표보다 많으면, 최소합은 넘은 것이므로 현재 길이가 최소 길이인지 확인하여 업데이트 한다.

✔️ 우리가 찾는 것은 "최소 길이"이므로, 최대한 적은 수를 합하는 것이 좋다.

 따라서 SUM값이 목표를 넘었을 경우에는 최소 길이를 찾아 왼쪽 포인터를 한 칸 증가시킨다.

 맨 왼쪽 값을 뺀 새로운 SUM값은, 다시 목표보다 큰지 적은지에 따라 새로 연산을 수행할 것이다.

 

 

 

 

 

 

 

 

 

💻 소스코드: 자바(Java)

public class Main_백준_1806_부분합_골드IV {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // input length
		int S = Integer.parseInt(st.nextToken()); // minimum sum
		int[] array = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}//input
		
		int left = 0, right = 0, sum = 0;
		int MAX = 100000001;
		int result = MAX;
		
		while(left<=right) {
			if(sum >= S) {
				result = Math.min(result, right-left);
				sum -= array[left++];
			}else if(right==N) break;
			else{
				sum += array[right++];
			}
		}
		System.out.println(result==MAX?0:result);
		
	}//end of main
}//end of class

 

 

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨