Algorithm(1)

2309 일곱 난쟁이

9개의 난쟁이 키가 주어지고 모두 100이 넘지 않는 자연수이다. 합이 100이 되게 하는 7개의 난쟁이 키를 찾아야 한다. 단, 합이 100이 되지 않는 경우는 없으며 정답이 여러가지이면 그 중 아무거나 출력한다.

결과는 오름차순으로 일곱 난쟁이의 키를 출력한다.

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	int n[9];
	int sum = 0;
	for (int i = 0; i < 9; i++)
	{
		cin >> n[i];
		sum += n[i];
	}
	sort(n, n + 9);

	int a, b, k;
	int flag = 0;
	for (int i = 0; i < 8; i++)
	{
		for (int j = i + 1; j < 9; j++)
		{
			k = n[i] + n[j];
			if (sum - k == 100)
			{
				a = i;
				b = j;
				flag = 1;
				break;
			}
		}
		if (flag == 1)
			break;
	}

	for (int i = 0; i < 9; i++)
	{
		if (i != a && i != b)
			cout << n[i] << endl;
	}

	return 0;
}

먼저 9개의 난쟁이 키를 sorting하고, 합이 100이 되는 7개를 찾는데, 계산을 줄이기 위해 전체 9명의 키에서 빼면 100이 되는 둘의 키를 찾아 제외했다.

1018 체스판 다시 칠하기

MN보드를 잘라 88크기 체스판으로 만드는데, 체스판을 잘라낸 후 몇개의 정사각형은 다시 칠해 변을 공유하는 두개 사각형은 항상 다른 색으로 칠해져 잇게 한다. 칠해야 하는 정사각형의 최소 개수를 구해야 한다.

자를 수 있는 모든 8*8에 대해 검은색으로 시작하는 체스판과 비교한 후, 가장 차이가 작은 값을 찾겠다. 다만, 흰색으로 시작하는 체스판의 경우는 검은색과 완전히 반대이므로 위의 값을 64에서 뺀 것으로 생각해야 한다.
따라서 검은색 체스판과 비교한 값들을 sorting한 후, (64-가장 큰 값)와 (가장 작은 값)을 비교해 둘 중 더 작은 값이 최소 수이다.

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

int compare(char B[8][8], char sliced[8][8])
{
	int num = 0;
	for (int i = 0; i < 8; i++)
		for (int j = 0; j < 8; j++)
		{
			if (sliced[i][j] != B[i][j])
				num++;
		}
	return num;
};
int main()
{
	int m, n;
	cin >> m >> n;
	char board[m][n];
	// board input
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> board[i][j];
		}
	}
	// board starting with B
	char B[8][8];
	for (int i = 0; i < 8; i++)
	{
		for (int j = 0; j < 8; j++)
		{
			if ((i + j) % 2 == 0)
				B[i][j] = 'B';
			else
				B[i][j] = 'W';
		}
	}

	char sliced[8][8];
	int arr[(m - 7) * (n - 7)];
	int a = 0;
	for (int i = 0; i < m - 7; i++)
	{
		for (int j = 0; j < n - 7; j++)
		{
			// make 8*8 sliced board
			for (int k = 0; k < 8; k++)
			{
				for (int l = 0; l < 8; l++)
				{
					sliced[k][l] = board[i + k][j + l];
				}
			}
			arr[a++] = compare(B, sliced);
		}
	}

	sort(arr, arr + (m - 7) * (n - 7));

	if (arr[0] < 64 - arr[(m - 7) * (n - 7) - 1])
		cout << arr[0] << endl;
	else
		cout << 64 - arr[(m - 7) * (n - 7) - 1] << endl;

	return 0;
}