백준 2805번 : 나무 자르기

문제 접근

---

1. 나무들을 정렬한 다음에 가장 높은 나무를 기준으로 자를 높이를 점점 낮춰가자고 생각했다.
   
     나무를 정렬한 뒤, 가장 높은 나무부터 현재 확인하고 있는 나무와 그다음 나무의 높이 차이를 height, 그리고 현재 확인하고 있는 나무가 몇 번째로 높은 나무인지는 width로 두고 M과 비교해 가며 높이를 낮춰갔다.
     
2. 최악의 케이스를 상정해 봤다.
   
     최대 나무 개수가 100만이고, 하나씩 확인하는 시간 복잡도는 O(n)이니 제한 시간 안에 충분히 동작 가능하다.

 

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

2805번: 나무 자르기

 

 

 

문제 코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long long N, M, height, width = 1, overheight_length = 0, ans=0;
	vector<int> tree;

	cin >> N >> M;

	tree.resize(N);

	for (int i = 0; i < N; ++i)
		cin >> tree[i];

	sort(tree.begin(), tree.end());

	while (tree.size() - width >= 0)
	{
		if (width != tree.size())
			height = tree[tree.size() - width] - tree[tree.size() - width - 1];

		else
			height = tree[0];

		if (height * width + overheight_length < M)
		{
			overheight_length += height * width++;
		}

		else
		{
			ans = tree[tree.size() - width] - (M - overheight_length) / width;

			if ((M - overheight_length) % width != 0)
				ans--;

			break;
		}
	}

	cout << ans << '\n';

	return 0;
}

 

 

 

느낀 점

---

    문제를 풀고 보니 해당 문제는 이분 탐색 문제였는데 혼자 이상하게 푼 것 같다. 다른 사람들은 조건을 만족하는 높이를 이분 탐색으로 찾아가는 방법으로 풀었지만, 나는 그냥 무식하게 높이를 낮춰가는 방식으로 풀었다. 뭐.. AC 받았으니 상관은 없지만, 조금 더 세련되게 풀 수 있도록 노력해 볼 필요가 있다.

 

1. 변수의 이름을 잘 설정하자.
   
     이번에도 마찬가지로 변수 이름을 애매하게 설정해서 문제를 풀 때 헷갈렸다. 조금이나마 직관적으로 바꿔 봤는데 이전 변수 명보다는 훨씬 괜찮아보이고 풀기에도 좋았다. 지금처럼 계속 직관적인 변수 명을 지어봐야겠다.
   
   
2. 변수를 초기화 할 때 default 값으로 초기화하자.
   
     어떻게 보면 당연한 이야기이지만 매번 별다른 고민 없이 모든 변수를 0으로 초기화를 하는 것 같다는 생각이 들었다. 이에 변수를 default 값으로 초기화한다면 조금이나마 코드를 직관적으로 작성할 수 있겠다는 생각을 했다.
   
   
3. 연산자 우선 순위를 생각하자.
   
     문제 제출 후 WA를 받았을 때, 순간 연산자 우선순위를 잘못 생각하고 있는지 고민하게 됐다. 이러한 고민을 한다는 건 정확히 이해하고 있지 않다는 것이니 다시 한번 제대로 확인할 필요가 있다.
   
     추가로 특정 수식의 경우, 연산자 우선 순위는 적절하더라도 사람이 보기에 바로 읽히지 않을 수도 있겠다는 생각을 했다. 따라서 수식을 작성할 경우, 우선순위가 높은 연산을 가능한 앞에 두어 직선적으로 이해할 수 있게 구성하는 게 좋을 것 같다.
   
   
4. 코드를 제출하기 전에 예제 외에 Edge case도 만들어서 테스트해보자.
   
     요즘 알고리즘 문제를 다시 풀면서 느끼는 거지만, 예제만 통과하면 생각 없이 제출하는 경향이 있다. 이건 CP가 아닌 PS이기에 예제가 맞더라도 반례를 고민해 보는 습관을 들일 필요가 있다. 특히 적어도 edge case 정도는 확인해 보고 넘어가도록 하자.