백준 #1799 - 비숍

문제 분석

백트래킹 문제, 노가다 문제이다.

대각선 방향으로 이동하므로 x+y, x-y로 묶어서 계산한다.

그런데 그냥 백트래킹으로 접근하면 TLE가 발생한다.

TLE 회피 아이디어

비숍은 체스판에서 같은 색상으로밖에 이동할 수 없다는 점을 이용하여,
2개의 문제로 나누어 답을 구한 뒤 둘을 합치면 원래 문제에 대한 답을 구할 수 있다.
이 경우 TLE는 아니지만, pypy3으로 10s가 넘는(AC라고는 나오지만) 시간이 걸린다.
문제 채점 priority가 낮아서 그런가보다.

반면 꽤 빠른 시간으로 푸는 풀이가 존재하는데, 이는 더 분석해봐야 겠다.

문제

https://www.acmicpc.net/problem/1799