[C++] 백준(BOJ) - 14627 : 파닭파닭

01 Apr 2024 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 14627 : 파닭파닭(링크)

평소 요리에 관심이 많은 승균이는 치킨집을 개업하였다. 승균이네 치킨집은 파닭이 주메뉴다. 승균이는 가게를 오픈하기 전에 남부시장에 들러서 길이가 일정하지 않은 파를 여러 개 구매하였다. 승균이는 파닭의 일정한 맛을 유지하기 위해 각각의 파닭에 같은 양의 파를 넣는다. 또 파닭 맛은 파의 양에 따라 좌우된다고 생각하기 때문에 될 수 있는 한 파의 양을 최대한 많이 넣으려고 한다. (하지만 하나의 파닭에는 하나 이상의 파가 들어가면 안 된다.) 힘든 하루를 마치고 승균이는 파닭을 만들고 남은 파를 라면에 넣어 먹으려고 한다. 이때 라면에 넣을 파의 양을 구하는 프로그램을 작성하시오. 승균이네 치킨집 자는 정수만 표현되기 때문에 정수의 크기로만 자를 수 있다.

입력

첫째 줄에 승균이가 시장에서 사 온 파의 개수 S(1 ≤ S ≤ 1,000,000), 그리고 주문받은 파닭의 수 C(1 ≤ C ≤ 1,000,000)가 입력된다. 파의 개수는 항상 파닭의 수를 넘지 않는다. (S ≤ C) 그 후, S 줄에 걸쳐 파의 길이 L(1 ≤ L ≤ 1,000,000,000)이 정수로 입력된다.

출력

승균이가 라면에 넣을 파의 양을 출력한다.

알고리즘

1. 이분탐색

풀이

• 이분탐색
  • 나눠야하는 파의 개수가 c로 일정하다 => cnt >= c를 이용 (최대 c값 까지)
  • 한번에 자를 수 있는 파의 범위를 아래에서부터 늘려나가는 방식도 있다

코드

// BOJ-14627 : 파닭파닭
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e18;

ll s, c, k, a[1000004], res, l = 1, r, mid, sum;

bool check(ll mid)
{
	ll cnt = 0;
	for (int i = 0; i < s; i++) cnt += a[i] / mid;
	return cnt >= c;
}

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];
	}

	l = 1, r = 1e9;
	while (l <= r)
	{
		mid = (l + r) / 2;
		if (check(mid))
		{
			res = mid;
			l = mid + 1; // 5개 이상으로 자를 수 있다면 파 길이 범위 늘리기
		}
		else r = mid - 1;
	}

	cout << sum - res * c << '\n';


	return 0;
}

평가

• 이분탐색 범위 설정 연습하기
• 무조건 r을 줄여 나가는 방법이 아니라 유동적으로 대처하기