1018번: 체스판 다시 칠하기
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
www.acmicpc.net
먼저, 흰색타일은 1, 검은색타일은 -1이라고 생각하고 풀어보자.
체스판에서 흰색타일(1) 옆은 반드시 검은색타일(-1), 검은색타일(-1) 옆은 반드시 흰색타일(1)이 온다.
따라서 시작타일을 1로 잡고 다음 타일을 검사할 때마다 -1 곱해주면 별도의 체스 보드판을 배열로 정의하지 않아도 문제를 해결할 수 있다.
|
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int MIN = 987654321;
vector<vector<int>> board;
int maxCol, maxRow;
int minCnt = MIN;
int min(int a, int b) { return a < b ? a : b; }
void Solution(int startY, int startX)
{
if (startY + 8 > maxCol || startX + 8 > maxRow) return;
int chk = 1;
int whiteCnt = 0;
int blackCnt = 0;
for (int i = startY; i < startY + 8; i++)
{
for (int j = startX; j < startX + 8; j++)
{
if (board[i][j] != chk) whiteCnt++;
else blackCnt++;
chk *= -1;
}
chk *= -1;
}
int cnt = min(whiteCnt, blackCnt);
minCnt = min(minCnt, cnt);
//if(startY+7 < maxCol) Solution(startY + 1, startX);
//if(startX+7 < maxRow) Solution(startY, startX + 1);
}
int main(void)
{
cin >> maxCol >> maxRow;
vector<int> temp;
for (int i = 0; i < maxCol; i++)
{
string wbStr;
cin >> wbStr;
for (int j = 0; j < maxRow; j++)
{
if (wbStr[j] == 'W') temp.push_back(1);
else temp.push_back(-1);
}
board.push_back(temp);
temp.clear();
}
for(int i=0; i < maxCol; i++)
for(int j=0; j < maxRow; j++)
Solution(i,j);
cout << minCnt << endl;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 8day
처음 컴파일할 땐 위에 주석처리한 코드를 통해 재귀호출했는데 시간초과가 났다. 한참을 삽질하다가
메인함수에서 반복호출하도록 바꿨더니 그제서야 정답 처리를 받을 수 있었다.
두 호출방법에서 어떤 시간차이가 발생했던건지 아직 잘 모르겠다.. 더 공부하면 알 수 있을까?
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 14500번: 테트로미노 (C++) (0) | 2020.04.15 |
|---|---|
| 백준 14889번: 스타트와 링크 (0) | 2020.04.14 |
| 백준 1182번: 부분수열의 합 (0) | 2020.04.13 |
| 백준 1966번: 프린터 큐 (0) | 2020.04.13 |
| 백준 14888번: 연산자 끼워넣기 (0) | 2020.04.12 |