[백준 / BOJ] 1018번 체스판 다시 칠하기 (C++, Python)

링크 : https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

---

문제

---

문제 풀이

난항을 겪었던 문제다. 어떻게 풀어야할지는 대충 감이 오는데, 구현이 잘 되지 않아 시행착오를 많이 겪었다.

 

체스판이 W, B 둘 중 하나의 패턴으로 시작한다. 가만히 생각해보면, W나 B가 맨 왼쪽 상단에 있을 때 W와 B의 위치가 정해지는 규칙이 나온다.

W가 (0, 0)에서부터 시작한다고 가정하면 (0, 2), (0, 4), (1, 1), (1, 3) ... 에 존재하는데, 이는 i행 j열이라 했을 때 i + j가 짝수인지, 홀수인지에 따라 W와 B의 위치가 정해진다.

 

이는 (i + j) % 2 == 0 or 1로 조건을 세울 수 있다. 나의 코드에서 핵심이 되는 부분은

 

if (((i + j) % 2 == 0 ? 'W' : 'B') != arr[i][j]) 

 -> cnt++;

 

인데, 풀어서 써보면 다음과 같다.

 

1) i + j가 짝수이면 W, 홀수이면 B라고 '가정'한다.

2) arr[i][j]가 W이거나 B면 cnt를 증가시킨다. (cnt는 덧칠해야하는 정사각형 수)

 

여기서 저 조건문은 맨 왼쪽 상단이 W일때를 가정했을 때이므로, 'W'와 'B'의 위치를 바꾸어도 답에는 전혀 영향이 없다. 이유는 후술하겠다. 아무튼 맨 왼쪽 상단이 W일 때, W는 i + j가 짝수인 위치에 존재해야 한다. 짝수에 위치하는 W가 arr[i][j]에 있는 색깔과 일치하지 않는다면 덧칠해야 하므로 cnt를 증가시킨다. B일때도 같은 로직을 따른다.

 

또한 잘 생각해보면, 위 코드는 W가 맨 왼쪽 상단일 때를 기준으로 잡았지만 W 기준에서 덧칠하지 않아도 되는 정사각형 갯수는 B를 기준으로 잡았을 때 덧칠해야 하는 정사각형 갯수이므로 마지막에 min(cnt, 64 - cnt); 코드를 넣어 (64 - cnt인 이유는 최댓값이 64이기 때문) 논리에 이상이 없도록 하였다.

 

뼈빠지게 고민하고 다른 분들 풀이를 보니 string으로 받고 미리 틀을 만들어놔 비교하는 방법도 있던데 아예 생각을 하지 못했었다.

 

파이썬으로는 삼항 연산자를 사용하지 않고 cnt를 2개로 만들어 풀었다. 기본적인 로직은 비슷하다.

 

 

C++ 코드 전문

 

Python 코드 전문

 

소감