티스토리 뷰

Algorithm

이진검색 - drying

Jinhyy 2018. 7. 30. 14:38
프로그램 명: drying
제한시간: 1 초

겨울에 빨래 한 후 옷을 말리는 것은 힘든 작업이다.

그러나 제인은 매우 깔끔한 성격이라 이 지루한 작업을 싫어하지 않는다. 그녀는 라디에이터를 이용해서 이 작업을 더 빨리 하기로 하였다. 그러나 라디에이터가 작아서 한 번에 한 벌의 옷만을 말릴 수 있다.

제인은 가능한 빠른 시간안에 모든 옷을 말리기를 원한다. 당신에게 젖은 옷들이 주어질 때 모든 옷을 말리는데 필요한 가장 빠른 시간을 계산 해 줄 것을 요청했다.

제인은 빨래 후 젖은 n 벌의 옷이 있다. 각 옷은 ai 만큼의 물을 머금고 있다. 매 분당 각 옷의 물의 양은 1 만큼 준다.(물론 , 옷이 아직 완전히 마르지 않은 상태에서 )

물의 양이 제로가 될 때 옷이 완전히 말려진 것이다.

매 분당 제인은 하나의 옷을 라디에이터에 말리기 위해서 선택할 수 있고, 라디에이터는 매우 뜨거워서, 매분 물의 양이 k 만큼 준다. 물의 양은 0 미만이 될수 없고 이 경우 물의 양은 0 이 된 것이다.

일은 라디에이터를 효과적으로 이용해서 옷 말리는 시간을 줄여야 하는 것이다. 옷 말리는 작업은 모든 옷을 말릴 때까지 계속 된다.

입력

  • 첫 라인은 정수 n 이 주어진다. (1 ≤ n ≤ 100 000).
  • 두 번째 줄에는 ai 가 주어진다.(1 ≤ ai ≤ 109)
  • 세 번째 라인은 k 가 주어진다.(1 ≤ k ≤ 109).

출력

모든 옷을 말리는 데 필요한 최소 시간을 출력한다.

입출력 예

입력

3
2 3 9
5

출력

3

입력

3
2 3 6
5

출력

2
출처: Northeastern Europe 2005, Northern Subregion


package drying;


import java.util.Arrays;

import java.util.Scanner;


class Main {


public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner scanner = new Scanner(System.in);

int n = Integer.parseInt(scanner.nextLine());

String[] tokens = scanner.nextLine().split(" ");

int k = Integer.parseInt(scanner.nextLine());

scanner.close();

int arr[] = new int[n];

int i=0;

while(i<n) {

arr[i]=Integer.parseInt(tokens[i]);

i++;

}

int count=0,sum=0;

Arrays.sort(arr);

while(true)

{

if(arr[n-1] < arr[n-2])

Arrays.sort(arr);

for(i=0;i<n-1;i++) {

if(arr[i]>0) {

arr[i]=arr[i]-1;

sum += arr[i];

}

else if(arr[i]==0)

sum += arr[i];

}

arr[n-1]=arr[n-1] - k;

if(arr[n-1]<0)

arr[n-1]=0;

sum += arr[n-1];

count++;

if(sum<=0)

break;

else

sum=0;

}

System.out.println(count);

}


}



'Algorithm' 카테고리의 다른 글

정렬 알고리즘 6개 정리  (0) 2018.08.22
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
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
글 보관함