관리 메뉴

공부공간

BOJ - 3020 ) 개똥벌레 본문

구현,시뮬

BOJ - 3020 ) 개똥벌레

개발자가될수있을까? 2021. 11. 3. 21:39
728x90


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

 

3020번: 개똥벌레

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이

www.acmicpc.net


석순의 높이를 정렬하여 만나는 개수를 COUNT해준다.

 

종유석의경우 동일하게 구한다음, 최종 높이에서 개수를 구할 때에 H-index번째의 개수를 참조한다.

 

 


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ3020 {
	
	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());
		int H = Integer.parseInt(st.nextToken());
		int h1[] = new int[N>>1];
		int h2[] = new int[N>>1];
		for(int i=0;i<N;i++) {
			int h = Integer.parseInt(br.readLine());
			if(i%2==0) {
				h1[i/2] = h;
			} else {
				h2[i/2] = h;
			}
		}
		Arrays.sort(h1);
		Arrays.sort(h2);
		
		int H1[] = new int[H+1];
		int H2[] = new int[H+1];
		int cnt =0;
		int pos =(N>>1)-1;
		int j;
		for(j=H;j>=0 && pos >=0 ;j--) {
			while(pos>=0&&j==h1[pos]) {
				cnt++;pos--;
			}
			H1[j]=cnt;
		}
		
		while(j>=1) {
			H1[j--] = cnt;
		}
		
		cnt=0;pos=(N>>1)-1;
		for(j=H;j>=0&&pos>=0 ;j--) {
			while(pos>=0&&j==h2[pos]) {
				cnt++;pos--;
			}
			H2[j]=cnt;
		}
		while(j>=1) {
			H2[j--] = cnt;
		}
		int answer =987654321;
		int answercnt=0;
		for(int i=1;i<=H;i++) {
			int now = H1[i]+H2[H-i+1];
			if(answer > now) {
				answer = now;
				answercnt=1;
			} else if(answer == now){
				answercnt++;
			}
		}
		System.out.println(answer+" "+answercnt);
	}
}

728x90

'구현,시뮬' 카테고리의 다른 글

BOJ - 3020 ) 개똥벌레  (1) 2021.11.03
BOJ - 5373 ) 큐빙  (0) 2021.10.02
[JAVA] Programmers 위클리 챌린지 1~8주 풀이  (1) 2021.09.30
BOJ - 1120 ) 문자열  (0) 2021.09.13
BOJ - 2417 ) 정수제곱근  (0) 2021.08.01
BOJ - 11728 ) 배열 합치기  (0) 2021.07.29
1 Comments
댓글쓰기 폼