글 읽기 - 반례 및 코드 질문드립니다 .. (제가 시도한 테스트 케이스 포함하였습니다)

totok682 4년 전 6

반례를 찾는 중인데 게시판의 웬만한 테스트 케이스를 써도 오류가 안납니다.

제가 짠 로직에 어느 부분이 잘못된건지 잘 이해가 안갑니다 ..ㅠㅠ

나무의 높이를 오름차순으로 정렬하고
제일 높은 나무의 높이부터 시작해서 lower_bound 함수를 통해 현재 절단기의 높이(cut_height)보다 높은 나무의 갯수를 셉니다
나무의 갯수(tree_num)와 길이(len)의 곱이 갖고자하는 나무의 길이보다 길어지면 반복문을 빠져나옵니다.
cut_height 을 1씩 줄이고 len을 1씩 늘리면서 2번부터 다시 반복합니다.

아래는 제가 시도했던 테스트 케이스는 코드 아래 써놓았습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> tree;

long long FindHeight(vector<int> tree, int need_height)
{
	long long height_sum = 0;
	long long cut_height = *(tree.end()-1); 
	long long len = 1;
	while (need_height > height_sum)
	{
		auto iter = lower_bound(tree.begin(), tree.end(), cut_height);
		int tree_num = distance(iter, tree.end());
		height_sum = tree_num * len;
		cut_height--;
		len++;
	}
	return cut_height;
}

int main()
{
	int N, M;
	cin >> N >> M;
	tree.reserve(N);
	for (int i = 0; i < N; i++)
	{
		int input;
		cin >> input;
		tree.push_back(input);
	}
	sort(tree.begin(), tree.end());
	cout << FindHeight(tree, M);

	return 0;
}



//// 테스트케이스
6 6
5 5 4 4 1 1
output : 3

2 3
2 2
output : 0

4 6
6 6 6 6
output : 4

4 8
2 2 2 2
output : 0

2 7
1 7
output : 0

4 10
2 3 4 5
output : 1

1 1
1000000000
output : 999999999

3 1
1 2 2
output : 1

2 6
8 8
output : 5

1 1
1
output : 0

6 6
6 6 6 6 6 6
output : 5

5 100
99 1 1 1 1
output : 0

2 50
51 1
output : 1

wjsqjawns 4년 전 6

반례입니다.

입력:
4 10
1 4 5 7

정답:
2

출력:
3

totok682 4년 전 1

wjsqjawns

끄악 감사합니다 로직 자체가 틀렸었네요 ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 및 코드 질문드립니다 .. (제가 시도한 테스트 케이스 포함하였습니다)

totok682 4년 전 6

wjsqjawns 4년 전 6

totok682 4년 전 1

wjsqjawns

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말