Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 우선순위큐
- java
- 알고리즘
- COSPROJAVA1급
- 다이나믹프로그래밍
- 취득후기
- 게더타운시작
- 엘라스틱서치
- 01BFS
- 세그먼트트리
- 백준코딩테스트
- 시뮬레이션
- 이젠 골드구현도 어렵네..
- spring
- 다익스트라
- dp
- COSPRO
- 완전탐색
- QUICKSTARTGUIDE
- 백준
- DFS
- deque
- PS
- 네트워크플로우
- 구현
- BFS
- 재귀함수
- YBMCOS
- 자바PS
- GatherTown
Archives
- Today
- Total
공부공간
BOJ - 1806 ) 부분합 본문
https://www.acmicpc.net/problem/1806
역시 이어서 투포인터 유형1번문제이다.
https://algorithmstudy-mju.tistory.com/120
위에 유형을 좀 정리해놓았다.
배열의 처음에 시작하여 목표숫자가 넘으면 개수를 세고, 그때의 s번째의 숫자를 빼준다.
다음 루프에서 목표숫자보다 작다면, e번째숫자를 더해준다.
위 작업을 반복하고, e가 맨마지막에서 목표숫자보다 클경우, 작을때까지 계속 빼주면서
사용된 숫자개수중 최소를 찾아간다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
int num[] = new int[n];
st = new StringTokenizer(br.readLine());
for(int i = 0 ; i < n ; i++) {
num[i] = Integer.parseInt(st.nextToken());
}
int sum = num[0];
int cnt = 1;
int answer = 100001;
for(int s=0,e=0 ;;) {
if(sum < t) {
e++;
if(e==n) break;
cnt++;
sum+=num[e];
} else if(sum >= t ) {
answer = answer > cnt ? cnt : answer;
cnt--;
sum-=num[s];
s++;
if(e==n-1) {
while(sum>=t) {
answer = answer > cnt ? cnt : answer;
cnt--;
sum-=num[s];
s++;
}
}
}
}
System.out.println((answer = answer ==100001 ? 0 : answer ));
}
}
'알고리즘 > 구현,시뮬' 카테고리의 다른 글
BOJ - 1647 ) 도시분할계획 (0) | 2020.07.07 |
---|---|
BOJ - 2230 ) 수 고르기 (0) | 2020.06.29 |
BOJ - 1644 ) 소수의 연속합 (0) | 2020.05.11 |
BOJ - 2470 ) 두 용액 (0) | 2020.05.11 |
BOJ - 2003 ) 수들의 합 2 (0) | 2020.05.11 |
Comments