[boj][c++] 16401 과자나눠주기, 14426 접두사찾기

16401 과자 나눠주기

오랜만에 그래프 탐색이 아닌 다른 문제를 풀어봤다. 자료 입력 조건이 최대 1e9이기 때문에 이진탐색을 이용해서 푸는 문제라는 감이 왔다. 처음 문제에 접근할 때는 m명의 조카에게 과자를 나눠줄 수 있는지, 잘라서 줘야한다면 그 개수를 어떻게 셀 것인지 등 지나치게 조건을 세분화하여 구현하려고 했다. 그랬더니 답을 이진 탐색한 뒤 가능한 값 중 가장 큰 값을 정답으로 출력한다는 초기의 아이디어가 희석되었다.

결국 명확한 설계를 그릴 수 없었기에 바로 코드 작성에 들어갔다. 초기 아이디어만 살리고 세세한 것은 코드를 짜면서 추가했다.

• 1과 1e9의 중간지점을 mid로 설정
• 답이 mid일 때 주어진 조건을 만족하는지 확인
  • 조건을 만족한다면 mid 기준 오른쪽 범위 탐색
  • 조건을 만족하지 않는다면 mid 기준 왼쪽 범위 탐색
• 2번 반복하여 조건을 만족하는 가장 큰 mid 출력

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

const int maxe = 1e9;
int arr[1000001];
int	n, m, l, r, ans;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> m >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	l = 1;
	r = maxe;
	while (l <= r)
	{
		int cnt = 0;
		int mid = (l + r) / 2;
		for (int i = 0; i < n; i++)
		{
			int temp = arr[i];
			while (temp >= mid)
			{
				cnt++;
				temp -= mid;
			}
		}
		if (cnt >= m)
		{
			ans = max(ans, mid);
			l = mid + 1;
		}
		else
			r = mid - 1;
	}
	cout << ans << endl;
}

---

14426 접두사 찾기

이 문제도 반복문을 많이 쓰고 자료도 적지 않아서 혹시나 했는데 역시 시간초과에 걸렸다.

<틀린 코드>

#include	<iostream>
#include	<string>
using namespace std;

int		n, m, ans;
bool	swc;
string	arr[10001];
string	pre[10001];
bool pre_swc[10001];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	for (int i = 0; i < m; i++)
	{
		cin >> pre[i];
	}
	for (int i = 0; i < n; i++)
	{
		string s = arr[i];
		for (int j = 0; j < m; j++)
		{
			string ns = pre[j];
			swc = false;
			for (int k = 0; k < ns.length(); k++)
			{
				if (s[k] != ns[k] || pre_swc[j] == true)
				{
					swc = true;
					break;
				}
			}
			if (swc == false)
			{
				ans++;
				pre_swc[j] = true;
			}
		}
	}
	cout << ans << endl;
}

코드를 전체적으로 뜯어고쳤다. 여기서 이진탐색하는 것은 n의 범위인데 m을 후순위로 입력받기 때문에 현재의 m과 전체 n을 비교한다.

• n은 다 입력받아서 저장하고 아스키순으로 정렬
• m을 입력받음
• 0과 n-1의 중간지점을 mid로 설정함
  • mid보다 입력받은 m이 작다면 끝지점을 mid -1로 설정
  • mid보다 입력받은 m이 크거나 같다면 시작지점을 mid + 1로 설정
  • substr 함수를 사용해 m이 n [mid]에 포함되는지 확인 후 3 반복

<맞은 코드>

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

int n, m, l, r, ans;
string s, ns;
vector<string>v;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> s;
		v.push_back(s);
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < m; i++)
	{
		cin >> ns;
		l = 0;
		r = n - 1;
		while (l <= r)
		{
			int mid = (l + r) / 2;
			if (ns < v[mid])
				r = mid - 1;
			else if (ns > v[mid])
				l = mid + 1;
			if (v[mid].substr(0, ns.length()) == ns)
			{
				ans++;
				break;
			}
		}
	}
	cout << ans << endl;
}

---

황금잔디

내 스트릭 완전 귀여워~~~~~~~ 칙칙한 회색 벗어나서 너무 행복하다! 골드 찍은지 좀 됐지만 깃허브에서 바뀐건 처음 봤는데 너무 귀엽다!!