14627 파닭파닭 문제 질문

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

6-I

작성

321

안녕하세요 문제 풀다가 질문이 생겨 글 올립니다.

http://boj.kr/dc7d38df2438415ab8eeb6bd946521ed

저는 위와 같이 코딩하였습니다.

최대 파의 길이를 구하는 로직은 맞는 것 같은데,

마지막 답을 구하는 과정에서 틀린 것 같습니다.

어떤 부분이 틀렸는지 알 수 있을까요?

C++코테 준비 같이 해요!

답변 1

큰돌

지식공유자

안녕하세요 ㅎㅎ 코드 다 확인했는데요. 다른 부분은 다 괜찮은데요.

혹시 다음 코드 왜 이렇게 짜신 건지 설명 가능할까요?

        // 왜 이렇게 하는거죠?
		ret += a[i] - (a[i] / ans) * ans;

bunny

질문자

치킨 하나에 들어가는 파 양이 ans일 때

ret += a[i] - (a[i] / ans) * ans;

파 길이 = a[i]

썰어서 없앤 부분의 길이 = (a[i] / ans) * ans

남은 양 += 파 길이 - 썰어서 없앤 부분의 길이

로 짰습니다.

큰돌

지식공유자

그렇게 하시면 안되고. 주문받은 파닭의 수를 기반으로 하셔야 합니다.

다음코드 참고해주세요.

#include <iostream>

using namespace std;

typedef long long ll;

ll s, c, ans, sum;
ll a[1000004];

int check(ll temp)
{
	ll cnt = 0;

	for (int i = 0; i < s; i++)
	{
		cnt += a[i] / temp;
	}

	if (cnt >= c) return 1;
	else return 0;

}


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

	cin >> s >> c;
	for (int i = 0; i < s; i++)
	{
		cin >> a[i];
        sum += a[i];
	}

	ll lo = 1;
	ll hi = 1e9;

	while (lo <= hi)
	{
		ll mid = (lo + hi) / (1ll * 2);

		if (check(mid))
		{
			ans = mid;
			lo = mid + 1;
		}
		else
		{
			hi = mid - 1;
		}
	}

	ll ret = 0;
	for (int i = 0; i < s; i++)
	{
		ret += a[i] - (a[i] / ans) * ans;
	}

	cout << sum - ans * c << "\n";




	return 0;
}

큰돌

지식공유자

첨언하자면 파를 주문한거를 기반으로 남은 거를 파악해야 하기 때문이에요

bunny

질문자

아 어떤 파는 잘리지 않을 수도 있는 경우가 있겠네요

질문 받아주셔서 감사합니다!

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

14627 파닭파닭 문제 질문