14627 파닭파닭 문제 질문!

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

6-I

해결된 질문

작성

160

수정됨

안녕하세요 항상 좋은 강의 감사합니다.

문제를 푸는 도중 의문점이 생겨 문의 드립니다.

저는 밑 코드처럼 코드를 짰는데,

제 생각에는 파닭에 넣을 파의 최대 길이(즉, high)값은 가장 짧은 파의 길이보다 길 수 없으므로 (왜냐면 2개의 파를 쓸수없기때문)

처음 입력을 받는 과정에서 min값을 구하여 그 값을 high로 설정하고 문제를 풀었습니다.

그런데 그 코드에서는 실패하고 선생님 코드처럼 high값을 1e9로 설정하여야 통과하더라고요

어떤 부분에서 문제점이 있는지 궁금합니다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll S, C, minnum=1000000000, num, msum, ret;

void solve(vector<ll>& vec) {
	ll lo = 1; // lo를 0으로 하게되면 mid가 0이되는 경우가 생겨 /0을 하게되어 오류가 나게된다.
	ll hi = minnum;
	ll mid;
	while (lo <= hi) {
		mid = (lo + hi) / (1LL * 2);
		ll cnt = 0;
		for (int i = 0; i < S; i++)
			cnt += vec[i] / mid;
		if (cnt >= C) { // 가능한 경우 더 줄여보기
			lo = mid + 1;
			ret = mid; // ret을 정해야하는 이유는 마지막으로 가능했던 수가 최종수가 되기 때문이다.
		}
		else {
			hi = mid - 1;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	vector<ll> vec;
	cin >> S >> C;
	for (int i = 0; i < S; i++) {
		cin >> num;
		minnum = min(minnum, num); // minnum을 구해야하는 이유는 최대 파의 양이기 때문이다.
		msum += num; // 총 파의양은 남는파의 양을 구할때 사용된다.
		vec.push_back(num);
	}
	solve(vec);
	cout << msum - ret*C << "\n";
	return 0;
}

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 조태님 ㅎㅎ

문제를 보시면

승균이는 파닭의 일정한 맛을 유지하기 위해 각각의 파닭에 같은 양의 파를 넣는다. 또 파닭 맛은 파의 양에 따라 좌우된다고 생각하기 때문에 될 수 있는 한 파의 양을 최대한 많이 넣으려고 한다. (하지만 하나의 파닭에는 하나 이상의 파가 들어가면 안 된다.) 힘든 하루를 마치고 승균이는 파닭을 만들고 남은 파를 라면에 넣어 먹으려고 한다. 이때 라면에 넣을 파의 양을 구하는 프로그램을 작성하시오. 승균이네 치킨집 자는 정수만 표현되기 때문에 정수의 크기로만 자를 수 있다.

같은 양의 파를 넣기 때문에 예를 들어

파가 4, 2, 1 이렇게 있을 때 1까지만 체크해야 하는 것 아니냐.

이렇게 생각할 수 있는데요.

좋은 생각이지만...

1부분을 안 쓸수도 있습니다.

예를 들어 파닭이 3개라면 파를 2, 2, 2 로 해놓고 나머지는 2가 되는게 아닐까요? 즉, 파 1을 쓰지는 않고도 해결할 수 있는 것이죠.

따라서 hi를 주어진 파의길이의 min으로 하는 것은 해당 반례를 해결하지 못합니다.

만약 주어진 입력을 기반으로 하실거면 max를 걸어서 하시면 됩니다.

minnum = max(minnum, num); // minnum을 구해야하는 이유는 최대 파의 양이기 때문이다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 AI 인턴

안녕하세요 조태님, 질문 주셔서 감사합니다.

문제에서 말씀하신 대로, 파닭에 넣을 파의 최대 길이인 high 값은 가장 짧은 파의 길이보다 짧거나 같아야 합니다. 따라서, high 값을 처음 입력받을 때 가장 짧은 파의 길이인 minnum으로 설정하는 것이 맞습니다.

코드를 살펴보면 while 문에서 mid 값이 사용되고, mid는 (lo + hi) / (1LL * 2)의 연산을 통해 결정됩니다. 이 때, hi 값이 1e9(10^9)로 설정되어야 하는 이유는 mid 값이 0이 되는 경우의 오류를 피하기 위해서입니다. lo는 이미 1로 설정되어 있기 때문에 mid가 0이 될 수 있다면, (lo + hi) / (1LL * 2)의 연산에서 lo 값과 동일한 값으로 결과가 나오게 됩니다. 이는 원하는 동작과 상이합니다.

따라서, hi 값을 충분히 큰 값으로 설정하여 mid 값이 0이 되지 않도록 하는 것이 필요합니다. 예를 들어 1e9로 설정하면 충분히 큰 값이므로 올바른 연산이 수행됩니다.

이와 같이 hi 값을 큰 값으로 설정하여 mid 값이 0이 되는 상황을 피할 수 있도록 해주셔야 합니다. 추가적으로 mid 값이 0이 되는 경우를 방지하는 이유는, 무한루프에 빠지거나, 0으로 나누기 연산을 하려고 할 때 발생하는 오류를 방지하기 위해서입니다.

문제 해결에 도움이 되셨길 바랍니다. 더 궁금한 점이 있다면 언제든지 질문해주세요! 감사합니다.

조태

질문자

lo값이 1인데 mid값이 어떻게 0이 될 수 있는 건가요?

hi값이 1일때까지만 while문이 동작하는데 그래도 1+1/1 을 계산하면

mid값의 최소는 1이 아닌가요?

인프런 커뮤니티 질문&답변

14627 파닭파닭 문제 질문!