결국 재색칠해야하는 횟수는 저 두가지의 체스판과 다른 색깔의 총합을 구하면 알 수 있는것이다.
이때 절대 간과해서는 안되는것이, WB, BW를 모두 고려해야한다는것이다. 이 문제의 오답률이 높은 이유는 대부분의 사람들이 주어진 필드가 검은색으로 시작했다면 BW로 생긴 체스판과 비교를 하며 최소값을 찾으려고 하는데, 사실 제일 처음 필드를 W로 재색칠하고 시작하는 경우가 더 최소값일 수 있다.
그래서 시작이 검정색일 경우와, 흰색일 경우를 각각 고려해서 함수를 짜서 문제를 해결하였다.
int WB_cnt(int x, int y)
{
int cnt = 0;
for(int i = 0; i < 8; i++)
{
for(int j = 0; j < 8; j++)
{
if(board[x+i][y+j] != WB[i][j])
cnt++;
}
}
return cnt;
}
int BW_cnt(int x, int y)
{
int cnt = 0;
for(int i = 0; i < 8; i++)
{
for(int j = 0; j < 8; j++)
{
if(board[x+i][y+j] != BW[i][j])
cnt++;
}
}
return cnt;
}
배열의 좌표 x,y를 받아온 후, 해당 위치를 첫 필드로 가지는 체스판이 검정색으로 먼저 시작할 경우 몇 번의 수정이 필요한지를 구하는지를 구하는 BW_cnt함수와 흰색으로 먼저 시작할 경우 몇 번의 수정이 필요한지를 구하는 WB_cnt 함수를 선언하였다.
그 후, 입력받은 보드의 크기를 고려하여, 8x8의 체스판을 생성할 수 있는 범위를 정하여, BW_cnt와 WB_cnt함수를 호출하고, 이중에 더 작은 값을 찾아가며 for문을 호출한다.
for(int i = 0; i + 8 <= N; i++)
{
for(int j = 0; j + 8 <= M; j++)
{
int tmp;
tmp = min(WB_cnt(i,j),BW_cnt(i,j));
if(tmp < min_val) {
min_val = tmp;
}
}
}
위와 같은 호출을 통해, 만들 수 있는 모든 체스판과 재색칠이 필요한 횟수를 구할 수 있다.
그리고 최종적으로 제일 작았던 값이 저장된 min_val을 출력시켜주면 해당 문제를 해결할 수 있다.
코드
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
using namespace std;
string WB[8] = {
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW"
};
string BW[8] = {
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB"
};
string board[50];
int WB_cnt(int x, int y)
{
int cnt = 0;
for(int i = 0; i < 8; i++)
{
for(int j = 0; j < 8; j++)
{
if(board[x+i][y+j] != WB[i][j])
cnt++;
}
}
return cnt;
}
int BW_cnt(int x, int y)
{
int cnt = 0;
for(int i = 0; i < 8; i++)
{
for(int j = 0; j < 8; j++)
{
if(board[x+i][y+j] != BW[i][j])
cnt++;
}
}
return cnt;
}
int main() {
int size[2];
int cnt;
int min_val = 12345;
pair<int, int> p1;
cin >> p1.first >> p1.second;
for(int i = 0; i < p1.first; i++)
cin >> board[i];
for(int i = 0; i + 8 <= p1.first; i++)
{
for(int j = 0; j + 8 <= p1.second; j++)
{
int tmp;
tmp = min(WB_cnt(i,j),BW_cnt(i,j));
if(tmp < min_val) {
min_val = tmp;
}
}
}
cout << min_val;
return 0;
}
평가
좌표계나 행렬 인덱스를 저장하기 좋은 pair라는 STL 자료형을 사용하며 공부할 수 있었던 문제이다.
또한 Brute Force 알고리즘의 대표적인 예시로, Brute Force는 이런 방식으로 풀이하면 된다는 느낌으로 포스팅을 진행하였다.
각 케이스마다 한 줄씩 평균을 넘는 학생들의 비율을 반올림하여 소수점 셋째 자리까지 출력한다.
풀이
이차원 배열의 동적 할당과 반복문을 활용하여 풀 수 있는 문제이다.
문제 자체가 정말 다양한 풀이법이 나올 수 있고, 굳이 이차원 배열이 아니고 다른 방법으로 푸는 방법도 있을 것이라고 생각된다.
먼저 테스트 케이스의 개수 C를 입력받은후, C개 만큼의 이차원배열 행을 동적할당한다.
int c;
scanf("%d",&c);
int **array = new int*[count];
float *means = new float[count]; //평균은 소수이므로 float자료형
그 후 학생의 수는 최대 1000명이라고 했으므로, 열 1000개와 학생 수 1에 해당하는 1001개의 동적할당을 진행해준다.
for (int i = 0; i < count; i++)
{
array[i] = new int[1001];
}
그 후엔, 학생들의 수를 입력받고, 해당하는 수 만큼의 점수를 입력받는다.
그 후 점수의 합을 통해 평균을 구하고, 평균을 넘은 학생들의 수를 세어 비율을 구하면 되는 문제이다.
이 때 소수 셋째자리에서 반올림을 하여 표현하라고 하였으므로,
%.3f 의 형식지정자를 사용하여 출력하면 원하는 출력값을 얻을 수 있다.
코드
#include <cstdio>
int main() {
int count;
scanf("%d",&count);
int **array = new int*[count];
float *means = new float[count];
int sum = 0;
int goodstudent = 0;
for (int i = 0; i < count; i++)
{
array[i] = new int[1001];
}
for (int i = 0; i < count; i++)
{
sum = 0;
scanf("%d",&array[i][0]);
for (int j = 1; j <= array[i][0]; j++)
{
scanf("%d",&array[i][j]);
sum += array[i][j];
}
means[i] = (float)sum / array[i][0];
for (int j = 1; j <=array[i][0]; j++)
{
if(array[i][j] > means[i])
{
goodstudent++;
}
}
printf("%.3f%%\n",(float)goodstudent/array[i][0] * 100);
goodstudent = 0;
}
return 0;
}
평가
이차원 배열 활용을 묻는 문제라고 생각된다.
배열의 첫 인자값이 점수가 아니고 학생의 수를 받아오기 때문에 반복문이 조금 복잡해질수는 있다. 필자의 코드도 완전 효율적인 코드는 아닐 수 있다고 생각한다. 이번 문제의 정답률은 38.361%로 매우 낮은편인데, 개인적으로는 왜 저렇게까지 낮은지는 이해가 되지 않는 문제였다. 본 문제에서는 이차원 배열과 동적할당에 대해서 알아두고 가면 좋을 것 같다고 생각한다.
