[코드트리] Sam의 피자학교 (삼성 SW 역량테스트 2021 하반기 오후 2번)

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/sam-pizza-school

이후 설명 및 입/출력은 링크 참고

 

Sam의 피자학교 문제 풀이는 BOJ 23291 : 어항 정리와 같다.

#include <stdio.h>

#define MAX (100 + 10)

int T;
int N, K;
int pizza[MAX][MAX];

/* 순서대로 오른쪽 : 1, 왼쪽 : 2, 위 : 3, 아래 : 4 */
int dr[] = { 0, 0, 0, -1, 1 };
int dc[] = { 0, 1, -1, 0, 0 };

void input()
{
	scanf("%d %d", &N, &K);

	for (int i = 0; i < MAX; i++)
		for (int k = 0; k < MAX; k++)
			pizza[i][k] = 0;

	for (int i = 1; i <= N; i++)
	{
		int f;

		scanf("%d", &f);
		pizza[N][i] = f;
	}
}

void output(int n)
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
			printf("%2d ", pizza[r][c]);
		putchar('\n');
	}

	putchar('\n');
}

void addFlour()
{
	int min = 0x7fff0000;
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (pizza[r][c] == 0) continue;
			if (pizza[r][c] < min) min = pizza[r][c];
		}
	}

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			if (pizza[r][c] == min) pizza[r][c]++;

}

void move()
{
	int start, width, height;

	start = width = height = 1;

	int i = 0;
	while (1)
	{
		if (start + width + height - 1 > N) break;

		for (int c = start; c < start + width; c++)
		{
			for (int r = N; r > N - height; r--)
			{
				int nr, nc;

				nr = N - width + c - start;
				nc = start + width + N - r;

				pizza[nr][nc] = pizza[r][c];
				pizza[r][c] = 0;
			}
		}

		if (i % 2) width++;
		else height++;

		start += (i / 2 + 1);

		i++;
	}
}

void sperad()
{
	int tmppizza[MAX][MAX] = { 0 };

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (pizza[r][c] > 0)
			{
				int save = pizza[r][c];

				for (int dir = 1; dir <= 4; dir++)
				{
					int nr, nc;

					nr = r + dr[dir];
					nc = c + dc[dir];

					if (pizza[nr][nc] == 0) continue;

					if (pizza[r][c] > pizza[nr][nc]) // 물고기가 많은 경우만 이동
					{
						int diff = (pizza[r][c] - pizza[nr][nc]) / 5;

						save -= diff;
						tmppizza[nr][nc] += diff;
					}
				}

				tmppizza[r][c] += save;
			}

		}
	}

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			pizza[r][c] = tmppizza[r][c];
}

void pizzaSort()
{
	int idx;
	int tmppizza[MAX][MAX] = { 0 };

	idx = 1;
	for (int c = 1; c <= N; c++)
	{
		if (pizza[N][c] == 0) continue;

		int row = N;
		while (1)
		{
			if (pizza[row][c] == 0) break;

			tmppizza[N][idx++] = pizza[row][c];
			row--;
		}
	}

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			pizza[r][c] = tmppizza[r][c];
}

void fold()
{
	int sc = N / 2 + 1;
	for (int c = N / 2; c >= 1; c--) pizza[N - 1][sc++] = pizza[N][c];
	for (int c = N / 2; c >= 1; c--) pizza[N][c] = 0;

	for (int r = N - 1; r <= N; r++)
	{
		int ec = N / 4 * 3;
		int fix = N;
		for (int c = N / 2 + 1; c <= ec; c++)
		{
			int nr, nc;

			nr = 2 * N - r - 3;
			nc = fix--;

			pizza[nr][nc] = pizza[r][c];
			pizza[r][c] = 0;
		}
	}
}

int check()
{
	int max = 0;
	int min = 0x7fff0000;
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (pizza[r][c] == 0) continue;
			if (pizza[r][c] < min) min = pizza[r][c];
			if (pizza[r][c] > max) max = pizza[r][c];
		}
	}

	if (max - min <= K) return 1;
	return 0;
}

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		int count = 0;

		while (1)
		{
			addFlour();
			move();
			sperad();
			pizzaSort();
			fold();
			sperad();
			pizzaSort();
			count++;

			if (check()) break;
		}

		printf("%d\n", count);
	}

	return 0;
}