BOJ 1806 부분합
https://www.acmicpc.net/problem/1806
- 입력값을 통해 누적합을 numbers에 세팅한다
- end를 하나씩 늘려가며 지금까지의 합이 S보다 크면
start시작인덱스를 뒤로 밀어 범위를 줄여본다 - 2번에서 줄인범위가 S보다 작아지면 다시 end값을 늘려 S와 비교한다
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;
public class Main {
private static int[] numbers; // 수열 리스트
private static int S; // 최소합
private static int N; // N개의 자연수
private static int answer; // 답
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());
answer = N; // 가능한 가장 큰 값으로 미리 세팅
S = Integer.parseInt(st.nextToken());
numbers = new int[N+1];
st = new StringTokenizer(br.readLine(), " ");
int start = 0; // 시작인덱스
for (int i = 1; i <= N; i++) {
int val = Integer.parseInt(st.nextToken());
numbers[i] = numbers[i-1]+val; // 지금까지 입력받은 숫자의 합 세팅
// start+1 인덱스 값 ~ i 인덱스까지의 합이 S보다 크다면
// start를 뒤로 밀 수 있다 => S보다 작아질때까지 뒤로 밀어서 업데이트
if(numbers[i]-numbers[start]>=S) {
start = getAnswer(start,i);
}
}
// N개의 숫자를 다 더해도 S보다 작다면 0 출력
if(numbers[N] < S) {
System.out.println(0);
}else {
System.out.println(answer);
}
}
/**start를 최대한 크게 변경하는 함수*/
private static int getAnswer(int start, int end) {
for (int i=0; i+start < end; i++) {
// start+i+1 부터 end번째 숫자의 합이 S보다 크다면 answer 업데이트
if(numbers[end]-numbers[start+i]>=S) {
answer = answer>end-start-i? end-start-i:answer;
}else { //start+i+1부터 end까지의 합이 S보다 작다면 해당 인덱스 리턴
return start+i;
}
}
// for문 끝나고 return되지 않았다 => start=end가 같은 값 => 1개의 합으로도 S보다 크다
answer = 1;
return end;
}
}
Author And Source
이 문제에 관하여(BOJ 1806 부분합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ok2qw66/BOJ-1806-부분합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)