n 크기의 정사각형이 하나 주어지고, 이 정사각형은 n²개의 단위 크기 작은 정사각형으로 나뉘어 있다고 가정해 보겠습니다. 그중 한 개의 작은 정사각형은 다른 색으로 칠여져 있습니다.
이제 큰 정사각형을 두 개의 동일한 부분으로 자르려고 할 때, 자르는 선이 색칠된 작은 정사각형과 어떤 점도 겹치지 않도록 잘라야 합니다. 또한 새롭게 잘린 두 조각이 서로 거울상(mirror image) 관계여야 한다는 조건도 함께 고려해야 합니다. 즉, 주어진 조건을 만족하도록 정사각형을 자를 수 있는지 판단하는 것이 문제이며, 입력으로는 n의 값과 색칠된 정사각형의 위치가 주어집니다.
예를 들어 size = 50, colored_row_pos = 25, colored_col_pos = 25가 입력으로 주어지면, 출력은 "Cutting is not possible"(자를 수 없음)이 됩니다.
해결 접근 방식
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- middle := size / 2의 내림 값(floor)을 계산합니다.
- (middle이 colored_row_pos 또는 colored_row_pos - 1과 같고) 그리고 (middle이 colored_col_pos 또는 colored_col_pos - 1과 같다면) 자르는 선이 색칠된 셀을 지나게 되므로 False를 반환합니다.
- 그 외의 경우에는 True를 반환합니다.
핵심 아이디어는 정사각형을 정확히 반으로 나누는 대칭 절단선이 반드시 중앙 부근(행과 열 기준 각각 middle, middle-1 위치)을 통과한다는 점입니다. 따라서 색칠된 셀이 바로 그 중앙 2×2 영역 안에 있다면, 어떤 방식으로 잘라도 절단선이 색칠된 셀과 만나게 되어 자르는 것이 불가능합니다.
구현 예제
def solve(size, colored_row_pos, colored_col_pos):
middle = size // 2
if (middle == colored_row_pos or middle == colored_row_pos - 1) and \
(middle == colored_col_pos or middle == colored_col_pos - 1):
print("Cutting is not possible")
else:
print("Cutting is possible")
size = 50
colored_row_pos, colored_col_pos = 25, 25
solve(size, colored_row_pos, colored_col_pos)입력
50, 25, 25
출력
Cutting is not possible
위 예제에서 색칠된 셀의 위치(25, 25)는 정사각형의 중앙 영역(24~25 행, 24~25 열)에 해당하므로, 대칭 절단선이 이 셀을 피할 수 없어 자르는 것이 불가능하다는 결과가 출력됩니다.