백준 나무자르기

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

 

나무자르기 문제이고 난이도는 Silver 3 이다. 보자마자 풀이가 생각날 정도로 쉬운 문제라고 생각했는데 왜 이게 silver 3 이나 되는지 의아했다.


그러나 보기좋게 fail...

문제를 다시 보니 정답률이 25%밖에 안되는 문제다. 나처럼 쉽게보고 덤볐다가 틀리는 사람이 많은가보다.


정답률이 낮다는건 모든 반례에 대해서 제대로 확인하는게 관건인 문제라고 볼 수 있다.
물론 소스코드를 오차 없이 설계하는것도 중요하다.

2110번: 공유기 설치

#include<iostream>

using namespace std;

#define INF 2000000000
int main(void) {

	int n, m;
	int tree[1000000];
	int left = 0, right = -INF;
	int mid = 0;
	long long ret = 0;
	long long treeLength = 0;
	cin >> n >> m;

	//나무 입력받기
	for (int i = 0; i < n; i++)
	{
		cin >> tree[i];
		if (tree[i] > right) right = tree[i];	//right은 최대값으로 시작
	}
	//left = 0;
	// H를 이진탐색하여 찾는다.
	while (left <= right)
	{
		treeLength = 0;
		mid = (left + right) / 2;
		
		//mid로 나무를 잘라보고 길이 총합을 대본다
		for (int i = 0; i < n; i++)
		{
			//mid보다 긴 나무만 잘라보면 돼
			if (tree[i] > mid)
			{
				treeLength += tree[i] - mid;
			}
		}

		//길이가 짧으면 mid를 낮춰야돼
		if (treeLength < m)
		{
			if (right == left)	//여기서 right == left가 걸리면 탐색이 끝난경우다. 앞으로 가능한 탐색이 없음.
			{
				break;
			}
			else
			{
				right = mid - 1;
			}
			
		}
		//길이가 길면(성공하면) mid를 높여서 탐색해봐
		//ret에 세이브하고 다음 탐색 들어가기
		else if (treeLength >= m)
		{
			ret = mid;
			left = mid + 1;
		}
		else // 예외
		{
			//printf("exception!!\n");
			return -1;
		}

	}

	cout << ret << endl;
	//printf("%d", ret);
	//예상 발생 문제 : 
	// 오른쪽 탐색을 한번도 안들어가고 끝날수도 있나?
	return 0;
}

이 문제에서 내가 신경쓰지 않은것은 3가지였다.
1. 초기 left범위 설정 실수. 나무를 자를 수 있는 범위는 0부터도 가능한데, 나무의 최소 길이를 left로 설정하는 실수를 함.
2. 자료형 설정 실수. int --> long long. 문제에서 요구하는 M의 범위는 20억 이하이지만 계산하면서 treeLength는 20억을 넘을 수 있기때문에 int보다 더 큰 long long이 필요.
★★★3. 종료조건시 값을 바꾸고 종료조건을 맞추는 소스를 짜지마라.

  if (treeLength < m)
		{
			if (right == left)	//여기서 right == left가 걸리면 탐색이 끝난경우다. 앞으로 가능한 탐색이 없음.
			{
				break;
			}
			else
			{
				right = mid - 1;
			}
			
		}
                     

이렇게 짜야하는 걸

  if (treeLength < m)
		{
            right = mid - 1;
			if (right == left)	//여기서 right == left가 걸리면 탐색이 끝난경우다. 앞으로 가능한 탐색이 없음.
				break;
		}
                     

이렇게 짰었다.
백준 구슬탈출2 문제에서도 종료조건 관련 실수를 했었는데... ㄷㄷ
어쨋든 종료조건은 값을 바꾸지 말고 확인한 다음에 종료조건이 아니면 그 다음에 값을 바꿔서 다음 case에 대해서 확인하는 식으로 소스를 작성해야한다.