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이 되는 둘의 키를 찾아 제외했다.
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;
}