백준 2805번 C/C++

www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

이 문제를 풀 때 가장 먼저 만들었던 코드이다,

이 문제의 난이도가 실버인데 실버가 이렇게 쉽게 풀릴리 없다고는 생각했지만 역시나 그럤다.

틀렸습니다가 아닌 시간 초과가 나왔고 다른 방식을 채택하기로 하였다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

//나무 M미터가 필요하다.
//절단기 작동 원리: 절단기에 높이 H를 지정한다. 그러면 톱날이 H만큼 올라간다.
//그러면 한줄에 속해 있는 나무를 모두 절단한다.
//그렇다면 H높이보다 높은 나무가 잘리고 H보다 작은 나무는 잘리지 않는다.
//내가 들고 가는 나무의 총 미터 수는 잘린 나무의 미터 수 이다. 
//즉 15, 8나무에서 H를 10으로 설정을 하면 5만큼만 획득가능하다. 
// H의 최댓값을 구하면 된다. 

int tree[1000000];
int main()
{   
   int n; //나무의 수 -> 벌목 하는 나무의 수
   int m; //내가 얻어야하는 나무의 총 길이
   scanf("%d %d", &n, &m);

   int max = -1;
   for (int i = 0; i < n; i++) {      //각 나무의 높이를 받는 for문이다.
      scanf("%d", &tree[i]);
      if (tree[i] > max) {
         max = tree[i];
      }
   }

   int length = 0;
   while (1) {
      max--;
      length = 0;

      for (int i = 0; i < n; i++) {
         if (tree[i] > max) {
            length = length + (tree[i] - max);
         }
      }

      if (length >= m) {
         break;
      }
   }

   printf("%d", max);
   
}

 

저번에 풀었었던 전선 자르기인가? 랜선자르기인가? 그거랑 비슷한 유형인 것 같아서 절반으로 나누어서 찾아보는 이분 탐색을 사용하였다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

//나무 M미터가 필요하다.
//절단기 작동 원리: 절단기에 높이 H를 지정한다. 그러면 톱날이 H만큼 올라간다.
//그러면 한줄에 속해 있는 나무를 모두 절단한다.
//그렇다면 H높이보다 높은 나무가 잘리고 H보다 작은 나무는 잘리지 않는다.
//내가 들고 가는 나무의 총 미터 수는 잘린 나무의 미터 수 이다. 
//즉 15, 8나무에서 H를 10으로 설정을 하면 5만큼만 획득가능하다. 
// H의 최댓값을 구하면 된다. 

long long tree[1000000];
int main()
{	
	int n; //나무의 수 -> 벌목 하는 나무의 수
	long long m; //내가 얻어야하는 나무의 총 길이
	scanf("%d %d", &n, &m);

	int max = -1;
	for (int i = 0; i < n; i++) {		//각 나무의 높이를 받는 for문이다.
		scanf("%d", &tree[i]);
		if (tree[i] > max) {
			max = tree[i];
		}
	}

	long long length = 0;
	int result = 0;
	int low = 0;  int high = max;

	while (low<=high) {
		int mid = (low + high) / 2;
		length = 0;

		for (int i = 0; i < n; i++) {
			if (mid < tree[i]) {
				length = length + (tree[i] - mid);
			}
		}

		if (length >= m) {
			if (result < mid) {
				result = mid;
			}
			low = mid + 1;
		}
		else {
			high = mid - 1;
		}

	}

	printf("%d", result);
	
}

역시 이러한 방식으로 진행을 하니 시간초과도 뜨지 않고 성공을 하였다.

위 코드와 또 다른 점을 찾을 수 있는데 int가 아닌 long long을 사용했다는 점이다.

int의 범위를 벗어나기 때문에 m과 length에 int를 사용하면 구해지지 않아서 틀렸습니다가 뜨게 됩니다.