백준 1806 부분합 / 자바 java
문제
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
출력
첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.
중심 아이디어
투포인터 알고리즘을 사용 함
시작포인터인 sp와 끝 포인터인 ep를 두고 둘 다 0에서 시작
가장짧은 길이를 저장하는 shortC를 0으로 두고 시작 -> 한개도 없을 경우 0 출력
ep<n 인 동안 반복해서 찾기
조건을 이상하게 줬다 했더니 왜 while문이 아니라 for문을 쓴거지?
sum의 값을 포인터가 둘다 0을 가르쳤을때의 합인 A[0]로 초기화 해두고 시작함
sum 과 m의 값을 비교해가며 반복문 돌기
1. sum이 m보다 작으면 더 많은 수를 포함해야 되므로 끝포인터를 하나 뒤로 이동시키고 sum에 A[ep]를 더하고 다시 반복문 시작으로 가기
2. sum이 m과 같거나 m보다 크면 shortC에 저장할지 말지 를 비교
shortC가 0이거나 현재 길이 (끝포인터-시작포인터+1) 보다 크다면 shortC에 현재길이를 저장
값이 작아져야 하므로 sum에서 시작포인터의 값 A[sp]을 빼고
시작포인터 한칸 뒤로
for (ep=0; ep>n;)
if(sum<m)
if (ep==n-1){
break;
}
ep++;
sum +=A[ep];
}
else {
if(shortC==0 || shortC>ep-sp+1) {
shortC = ep - sp + 1;
}
sum -= A[sp];
sp++;
}
}
고민한 부분
처음에 문제를 잘못읽어서 고민함..... m과 같을 때만 카운트한다고 생각해서 틀림 -> 문제를 잘 읽자
ep=n-1일때 sum<m이면 ep를 하나 뒤로 이동해서 인덱스 범위를 벗어나는 오류 발생 -> sum<m이면서 ep=n-1이면 반복문을 탈출하는 예외를 주어 해결
제출한 전체코드
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int sp= 0, ep =0, shortC=0;
int n = sc.nextInt(); //수열의 길이
int m = sc.nextInt(); //구해야하는 합의 크기
int A[] = new int[n];
for (int i=0; i<n; i++){
A[i] = sc.nextInt();
} //수열 입력받기
int sum = A[0];
for (ep=0; ep<n;){
if(sum<m){
if (ep==n-1){
break;
}
ep++;
sum +=A[ep];
}
else {
if(shortC==0 || shortC>ep-sp+1) {
shortC = ep - sp + 1;
}
sum -= A[sp];
sp++;
}
}
System.out.println(shortC);
}
}