글 읽기 - 왜 이 방법은 맞았는데, 이 방법은 틀렸나요??

persona_k 4년 전 0

안녕하세요.

해당 문제에 대해서 의문점이 있어서 글을 쓰게 되었습니다.

해당 나무 자르기를 오름차순으로 정렬한 다음 이분 탐색으로 문제를 해결했습니다.

다만 범위의 기준에서 다음과 같은 결과가 있었습니다.

첫번째로 풀었을 때는 해당 나무의 입력을 오름차순으로 정렬한 다음, 가장 첫 번째 원소와 int형의 최대값 사이를 기준으로 탐색한 결과 -> 실패

left = 나무 중에서 가장 작은 나무의 길이

right = int형의 최댓값

두번째로 풀었을 때는 0부터 시작해서 int형의 최댓값 -> 성공

left = 0

right = int형의 최댓값

왜 0부터 시작을 해야할까요?...

읽어주셔서 감사합니다.

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

int n,m;
vector<int> tree;
long long sum, ans;

void cutting(long long left, long long right){
	if(left<=right){
		long long mid = (left+right)/2;
		sum = 0;
		int cycle = tree.size();
		for(int i=0; i<cycle; i++){
			if(tree[i]-mid < 0) continue;
			sum+=(tree[i]-mid);	
		}
		//cout<<mid<<' '<<sum<<endl;
	
		if(sum >= m){
		    ans = mid;
			cutting(mid+1, right);	
		}
		else{
			cutting(left, mid-1);
		}
	}
}

int main(){
	cin>>n>>m;
	for(int i=0; i<n; i++){
		int temp;
		cin>>temp;
		tree.push_back(temp);
	}
	
	sort(tree.begin(),tree.end());
	cutting(0, INT_MAX);
	cout<<ans;
	return 0;
}

djm03178 4년 전 0

가장 작은 나무의 길이로 설정하면 그 나무는 아예 못 자를 뿐 아니라, 더 아래까지 자르면 더 많은 나무를 얻을 수 있음에도 불구하고 시도해보지 않기 때문입니다.

그리고 질문을 올릴 때는 맞은 코드 말고 틀린 코드를 올려주세요. 틀린 코드를 정확하게 어떻게 짜셨는지 제가 한 글자도 다름없이 그대로 재현할 수 없기 때문에 반례도 드릴 수가 없습니다.

persona_k 4년 전 0

@djm03178

답변 감사합니다.

아래가 틀린 코드입니다.

시작범위를 트리의 가장 작은 높이에서 int형의 최댓값까지 이분 탐색을 돌린 내용입니다.

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

int n,m;
vector<int> tree;
long long sum, ans;

void cutting(long long left, long long right){
	if(left<=right){
		long long mid = (left+right)/2;
		sum = 0;
		int cycle = tree.size();
		for(int i=0; i<cycle; i++){
			if(tree[i]-mid < 0) continue;
			sum+=(tree[i]-mid);	
		}
		//cout<<mid<<' '<<sum<<endl;
		ans = mid;
		if(sum >= m){
			cutting(mid+1, right);	
		}
		else{
			cutting(left, mid-1);
		}
	}
}

int main(){
	cin>>n>>m;
	for(int i=0; i<n; i++){
		int temp;
		cin>>temp;
		tree.push_back(temp);
	}
	
	sort(tree.begin(),tree.end());
	cutting(tree[0], INT_MAX);
	cout<<ans;
	return 0;
}

djm03178 4년 전 1

제 답변을 이해하셨다면 반례도 필요 없을 것인데, 한 번 고민은 해보셨는지요.

1 1
2

persona_k 4년 전 0

@djm03178

답변 감사합니다.

주신 반례를 확인해보니, 만약이 2로 나무를 자른다면 상근이가 필요한 1m의 나무를 가져갈 방도가 없네요.

따라서 그보다 더 작은 수로 탐색으로 시도해봐야한다는 거군요.

덕분에 이해가 됬습니다. 정말 감사합니다.

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

문제

문제

출처

ICPC

왜 이 방법은 맞았는데, 이 방법은 틀렸나요??

persona_k 4년 전 0

djm03178 4년 전 0

persona_k 4년 전 0

djm03178 4년 전 1

persona_k 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말