백준 2805번

• 절단기에 설정할 수 있는 높이는 0이상의 정수.
• 적어도 M미터의 나무를 얻기 위해 , 절단기에 설정 할 수 있는 높이의 최댓값 구하기.
• 설정가능 높이로 0도 가능하기 때문에, 나무의 높이의 합이 항상 M보다 크거나 같으면, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다.
• 1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000
• 0 ≤ 높이H ≤ 1,000,000,000

문제해결방법

• 이문제가 나의 정답률을 매우 많이 낮춰주었다.

• 처음 이 문제를 풀 때는 .. arr에다가 나무의길이들을 넣고, 각 element에서 x를 뺀다고 가정하고 x를 순차적으로 찾는.. 노가다를 했으니 당연히 시간 초과가 나왔다. → 이진탐색처럼 O(logn)으로 풀이할 방법을 떠올 릴 수 있어야 한다.

• 그러고 블로그를 돌아다녀보니 이진탐색으로 풀어야 한다는 것 까지 알고는 수많은 틀렸습니다에 성질을 못이기고 포기했었다.

• 그리고 다시 푸는데 또 틀렸다..맞은 사람들이랑 알고리즘은 같은데 왜틀릴까 → 다르기 때문.

• 생각과정

  • 먼저 각 나무의 길이를 v 배열에 저장한다

  • 나무의 길이를 받으면서 나무길이 중 max값을 찾는다. : 왜냐면, 0~ max 값 사이의 H가 되긴해야할 것 아닌가 . 그래서 max를 알아야만 했음.

    • 갠적으로 vector에다가 담아두고 cpp에 이미 있는 quicksort 알고리즘을 사용해서 sorting을 시키고 마지막 element를 받아오면 nlogn이 나오니 좋은 것 아닌가 했는데 → 이게 시간 더 오래 걸린다. O(n^2)> O(nlogn) > O(n)

      for (int i = 0; i < n; i++)
      	{
      		long long temp;
      		cin >> temp;
      		v.push_back(temp);
      	}
      	sort(v.begin(), v.end()); //오름차순

    • 나무의 길이를 받는 때 마다 if문 안에 비교구문을 사용해서 max를 구한다면 O(n)만큼의 시간복잡도면 될 것. <비교문이 n번 실행된다 >

      	for (int i = 0; i < n; i++)
      	{
      		long long temp;
      		scanf("%lld", &temp);
      		//cin >> temp;
      		v[i] = temp;
      		if (temp > max) max = temp;
      	}

  • 그 후 , 0 ~ max에서 이진탐색을 하면서 최대의 H를 찾는다.

    • 이때 이진탐색의 기준은, h를 v의 element 에서 뺀 값을 모두 sum한 것이 M보다 큰지 작은지 같은지를 기준으로 하며 range를 변화시킨다.
    • sum : (v[0]-h) +(v[1]-h) +.....+(v[end]-h)
      • sum > M : sum을 줄여도 "된다" - h를 더 높일 수 있다. 우리는 h의 최댓값을 찾는 것이기 때문에, h를 높인다 → 우측으로 range를 좁힌다 : start = h_prev+1
      • sum < M : sum 높"여야만 한다" - "적어도 M을 넘어야 하기 때문"이다. h를 낮춘다 → 좌측으로 range 를 좁힌다 : end = h_prev -1 .

• 후 <실패> _ 일단 long long 타입으로 다 변경해봄 : 각 나무의 길이가 최대 10억이기 때문에, signed int는 최대 21억까지 가능하기에 total_sum을 longlong으로 해야했고, 이를 유지하기 위해 그냥 모든 type을 long long으로 했다.

• 그래도 틀렸었 고_ 다른 분과의 코드와 비교해서 차이점을 찾았다 :

1. 생각하던것: sum == M 인 경우 : 여기서 h를 더 올린다면 sum 이 M보다 작아지기 때문에 이 때의 mid값을 취하고 종료해야 최대H 라고 생각했다.
2. 생각하던것: sum > M 인 경우 : sum > M 이기 때문에 H를 더 올릴 수 있다(우리는 H의 최댓값을 찾아야 하니까.). 따라서, start를 조정하게 된다. 그래서 아래와 같은 코드가 나왔는데 , 단순히 아래 코드 처럼 한 경우의 문제점
   1. sum > M 인경우, start를 조정하고 start ≤ end를 만족해서, loop에 들어간 경우, 이 때는 sum < M 이 나온 경우. 이에 따라서 end를 조정했는데 이번엔 start > end이 되어 loop을 나오게 된 경우. mid는 결국 sum<M일 때의 mid값인데 이 값을 h에 넣는 것이 되기 때문에 틀린 결과가 나오게 되는 것이다.
   2. 그니까 여기서 치명적인 문제점은 ! loop를 벗어나고 나서 h 에 mid값을 넣는 것 때문!

long long start=0,end=max,mid,h=0;
while(start<=end)
{
	mid = (start+end)/2;
	sum = sum_arr(h);
	if(sum < M) end = mid-1; // H를 줄이기 
	else if( sum > M) start = mid+1;  // H를 높이기 
	else  break;
}
h = mid; 

• 그래서 고친 코드

long long start =0,end=max,mid,h=0;
while(start<=end)
{
	mid = (start+end)/2;
	sum = sum_arr(h);
	if(sum < M) end = mid-1; // H를 줄이기 
	else if( sum > M) {
			h = mid;
			start = mid+1;  // H를 높이기 
	}
	else  {
			h = mid;
			break;
	}
}

• 정답 뜬 코드 :실행시간 220ms

  #include <iostream>
  #include <vector>
  #include <algorithm>
  #include <stdio.h>
  
  using namespace std;
  
  long long n, m;
  long long v[1000000];
  
  // n은 1백만 이하, 각 나무의 높이는 최대 10억. 따라서 total_sum은 long long 타입이어야 한다. 
  long long sum_arr(long long H)
  {
  	long long sum = 0;
  	for (int i = 0; i < n; i++) {
  		sum += ((v[i] - H) > 0)*(v[i] - H); // v[i]-H 값을 sum 하기 위함. 0보다 작은 경우 0을 더한다.
  	}
  	return sum;
  }
  // long long
  long long bi_search(long long a_start, long long a_end)
  {
  	long long start = a_start, end = a_end, h=0,mid; // mid = h
  	while (start <= end)  // binar searhc의 종료 조건
  	{
  		long long sum;
  		mid = (start + end) / 2;
  		sum = sum_arr(mid);
  		if (sum < m) { // h를 감소시키는 과정
  			end = mid - 1;
  		}
  		else if (sum > m) { // h를 증가시킨다.
  			h = mid;
  			start = mid + 1;
  		}
  		else {  // 더 이상 h를 건들이지 않는다.
  			h = mid;
  			break;
  		}
  	}
  	
  	return h;
  }
  
  int main()
  {
  	long long h, max = 0;
  	//cin >> n >> m;
  	scanf("%lld%lld", &n, &m);
  
  	for (int i = 0; i < n; i++)
  	{
  		long long temp;
  		scanf("%lld", &temp);
  		//cin >> temp;
  		v[i] = temp;
  		if (temp > max) max = temp;
  	}
  	long long start = 0, end = max;
  	h = bi_search(start, end);
  
  	printf("%lld\n", h);
  }

• 이를 좀더 깔끔하게

  • sum == M 인 경우, 만약 욕심내서 start = mid+1 을 하게 되면, 해당 range에서는 절대 sum≥m 인 것을 찾을 수 없게 되어, 결국 start>end로 종결하게 되고, sum==m일 때의 mid값이 h에 위치하게 될 것이기에, sum≥M인 경우로 같이 적어 줄 수 있다.

  • 근데 이러면, 기존엔 sum == M 이면 바로 break하던 것에서 무의미하게 더 loop을 돌며 end>start일 때 까지 더 도는게 되어서 , 4ms정도 시간이 더 늘어나게 되었음.

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <stdio.h>
    
    using namespace std;
    
    long long n, m;
    long long v[1000001];
    
    // n은 1백만 이하, 각 나무의 높이는 최대 10억. 따라서 total_sum은 long long 타입이어야 한다. 
    // long long
    long long bi_search(long long a_start, long long a_end)
    {
    	long long start = a_start, end = a_end, h=0,mid; // mid = h
    	while (start <= end)
    	{
    		long long sum=0;
    		mid = (start + end) / 2;
    		for (int i=0;i<n;i++)
    			sum+= ((v[i] - mid) > 0)*(v[i] - mid);
    
    		if (sum < m) { // h를 감소시키는 과정
    			end = mid - 1;
    		}
    		else if (sum >= m) { //h를 증가시킨다. 
    			h = mid;
    			start = mid + 1;
    		}
    	}
    	return h;
    }
    
    int main()
    {
    	long long h, max = 0;
    	cin >> n >> m;
    
    	for (int i = 0; i < n; i++)
    	{
    		long long temp;
    		scanf("%lld", &temp);
    		//cin >> temp;
    		v[i] = temp;
    		if (temp > max) max = temp;
    	}
    	long long start = 0, end = max;
    	h = bi_search(start, end);
    
    	printf("%lld\n", h);
    }