백준 25596번 마트료시카 박스 II

문제 링크입니다: https://www.acmicpc.net/problem/25596

25596번: 마트료시카 박스 II

큐 배열을 이용하여 푼 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. N이 최대 1,000이고 K 또한 최대 1,000이므로 크기가 2,000이 넘는 큐 배열을 선언해줍니다. 

2. 주어진 입력을 토대로 1번에서 선언한 큐 배열을 전처리해줍니다.

3. 모든 박스를 순회하며 서브 박스의 개수가 M개 이하인지 확인하고 M개 초과라면 아래와 같이 처리해줍니다.

3.1 각 박스의 서브 박스가 M개 이하가 될 때까지 새로운 박스를 서브 박스로 추가하고 해당 서브 박스에 기존 서브 박스를 중첩합니다.

3.2 이 과정에서 추가한 박스가 K개가 넘어갈 경우 불가능한 케이스이므로 0을 출력하고 프로그램을 종료합니다.

4. 3번 과정을 통과하면 가능한 케이스이므로 1과 추가한 박스 개수를 출력합니다.

4.1 그리고 1부터 (N + 추가한 박스 개수)를 순회하며 해당 박스의 서브 박스 개수와 서브 박스들을 출력하고 프로그램을 종료합니다.

 

	#include <iostream>
	#include <queue>
	using namespace std;
	const int MAX = 2000 + 20;
	queue<int> q[MAX];
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N, M, K;
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++)
	{
	int cnt;
	cin >> cnt;
	for (int c = 0; c < cnt; c++)
	{
	int box;
	cin >> box;
	q[i].push(box);
	}
	}
	int extra = 0;
	for (int i = 1; i <= N && extra <= K; i++)
	{
	while (true)
	{
	if (q[i].size() <= M)
	{
	break;
	}
	if (++extra > K)
	{
	cout << 0 << "\n";
	return 0;
	}
	for (int k = 0; k < M; k++)
	{
	q[N + extra].push(q[i].front());
	q[i].pop();
	}
	q[i].push(N + extra);
	}
	}
	cout << 1 << "\n" << extra << "\n";
	for (int i = 1; i <= N + extra; i++)
	{
	cout << q[i].size();
	while (!q[i].empty())
	{
	cout << " " << q[i].front();
	q[i].pop();
	}
	cout << "\n";
	}
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2022

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~