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 |
Tags
- 다이나믹프로그래밍
- BFS
- dp
- 엘라스틱서치
- spring
- deque
- 백준코딩테스트
- GatherTown
- 01BFS
- java
- 완전탐색
- 다익스트라
- 시뮬레이션
- QUICKSTARTGUIDE
- DFS
- YBMCOS
- 세그먼트트리
- 백준
- COSPRO
- 재귀함수
- COSPROJAVA1급
- 구현
- PS
- 자바PS
- 네트워크플로우
- 이젠 골드구현도 어렵네..
- 취득후기
- 알고리즘
- 게더타운시작
- 우선순위큐
Archives
- Today
- Total
공부공간
BOJ - 2473 ) 세용액 본문
https://www.acmicpc.net/problem/2473
세용액의 합이 0 이 가까운 것은 고르기 위해서, 정렬후 앞쪽부터 O(n)만큼 순차탐색을 하도록하자.
세개의 포인터를 사용해야하기때문에, 하나는 고정시키고 두개를돌려주자
5000^2으로 충분하다
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class 세용액 {
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());
long arr[] = new long[n];
long answer = Long.MAX_VALUE ;
st = new StringTokenizer(br.readLine());
for(int i = 0 ; i < n ; i ++) { arr[i] = Long.parseLong(st.nextToken());}
Arrays.sort(arr);
int s=0,m=0,e=n-1;
int i1=0,i2=0,i3=0;
top:
for( s=0 ; s < n ; s++) {
long now = arr[s];
m = s+1;
e = n-1;
if(m >=n && e <=m) continue;
for( ; m < e ;) {
long snumber = arr[m];
long enumber = arr[e];
long sum = now+ snumber + enumber;
if(Math.abs(sum) < Math.abs(answer)) {
answer = sum;
i1=s;i2=m;i3=e;
}
if(sum >0)e--;
else if(sum==0) break top;
else {m++; }
}
}System.out.print(arr[i1] +" "+arr[i2] + " "+arr[i3]);
}
}
'알고리즘 > 이분탐색' 카테고리의 다른 글
BOJ - 8983 ) 사냥꾼 (0) | 2020.10.01 |
---|---|
BOJ - 2110 ) 공유기 설치 (0) | 2019.12.17 |
BOJ - 2805 ) 나무자르기 (0) | 2019.12.17 |
BOJ - 2512 ) 예산 (0) | 2019.12.16 |
Comments