[백준 13437] 슈퍼 나이트

티어: 실3

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

해설을 읽기 전에, 분명 맞은 것 같은데 틀렸다면 overflow를 체크해보자. 필자도 이걸로 아까운 시간을 날렸었다..

지문을 자세히 보면, $2 \times \max(a, b) < \min(N, M)$이라는 조건을 확인할 수 있다. 이를 유념하며 문제를 풀어보자.

여기서는 $a, b$는 순서가 바뀌어도 일반성을 잃지 않기 때문에, $a < b$라고 가정했다. $N, M$도 마찬가지이기 때문에 $N < M$이라고 가정했다.

$k = 0$#

움직일 수 있는 칸이 없는 위치가 존재하려면, $2 \times b > N$을 만족해야 한다. 당연하게도 조건에 의해 이런 테스트케이스는 존재하지 않는다. 따라서 $k = 0$일 때는 항상 0을 출력하면 된다.

$k = 1, 5, 7$#

갈 수 있는 칸의 개수가 1, 5, 7이라는 건 각각 7칸, 3칸, 1칸을 갈 수 없어야 한다는 뜻인데, 문제에서는 다른 기물이 없으므로 오로지 체스판 밖으로 나가기 때문에 갈 수 없는 칸만 존재한다. 나이트의 움직임은 x축, y축 대칭이므로 x좌표 또는 y좌표가 같은 위치가 총 4쌍이 존재하며, 체스판은 항상 직사각형 모양이기 때문에 $k = 3$을 제외하고는 항상 짝수 개의 칸만 체스판 밖으로 나가게 된다. 즉 이 경우에도 항상 0을 출력하면 된다.

$k = 2$#

조금만 생각해보면 체스판의 꼭짓점 부분만 가능하다는 걸 알 수 있다. 조금 더 엄밀히 들어가면, 꼭짓점을 기준으로 $a$칸 이내의 정사각형 범위에서 가능하다. $k$값이 2에서 3으로 바뀌려면 x좌표 또는 y좌표가 같은 1쌍이 생겨나야 하는데, 당연하게도 $a < b$이므로 $a$칸 움직였을 때 1칸이 먼저 나타나게 된다. 꼭짓점은 총 4개가 존재하므로 $4 \times a \times a$를 출력하면 된다.

$k = 3$#

$k = 2$와 $k = 4$ 사이에 존재하는 부분이다. $k = 4$일 때는 x좌표 또는 y좌표가 같은 2쌍이 존재하게 되는데, $k = 3$일 때는 $a$거리의 칸은 존재하면서 $b$거리의 칸은 존재하지 않는 위치일 때만 성립하게 된다. 따라서 $(b - a) \times a$칸만큼을 차지하며, 8개의 구역이 존재하므로 $8 \times a \times (b - a)$를 출력하면 된다.

$k = 4$#

꼭짓점 구역과 모서리 구역으로 나뉘어진다. 꼭짓점 구역은 x좌표가 같은 1쌍과 y좌표가 같은 1쌍이 이동 가능한 칸들을 이루고, 모서리 구역은 x좌표 또는 y좌표가 같은 2쌍이 이동 가능한 칸들을 이룬다. 모서리 구역의 길이는 각각 $N - 2b$, $M - 2b$이고 1쌍씩 존재하기 때문에 $2 \times a \times (N + M - 4 \times b)$개이다. 꼭짓점 구역은 $b^2$에서 $k = 2$, $k = 3$인 경우인 $a^2$과 $2 \times a \times (b - a)$만큼을 빼면 된다. 즉, $(b - a)^2$이고 꼭짓점은 총 4개가 존재하므로 $4 \times (b - a)^2$이다. 최종적으로 두 구역을 합해 $4 \times (b - a) \times (b - a) + 2 \times a \times (N + M - 4 \times b)$를 출력하면 된다.

$k = 6$#

$k = 4$일 때 모서리 구역과 거의 일치한다. 다만 $k = 6$이기 위해서는 x좌표 또는 y좌표가 같은 3쌍이 이동 가능한 칸들을 이뤄야 하기 때문에 $k = 4$일 때보다 모서리에서 조금 더 떨어져 있어야 하고, 그 범위는 3번째 쌍이 존재하면서 4번째 쌍이 존재하지 않는 $b - a$만큼의 칸이다.

따라서 $2 \times (b - a) \times (N + M - 4 \times b)$를 출력하면 된다.

$k = 8$#

임의의 칸을 기준으로 상하좌우 모두 $b$칸만큼의 여유가 있다면 $k = 8$이라고 할 수 있다. 반대로 생각하면, 이걸 만족하는 칸은 $(N - 2b)(M - 2b)$개가 있다는 뜻이다. 따라서 $(N - 2 \times b)(M - 2 \times b)$를 출력하면 된다.

var [a,b,N,M,k] = require('fs').readFileSync(0).toString().trim().split(" ").map(e=>+e);
var [a,b,N,M] = [a,b,N,M].map(f=>BigInt(f))
var [a,b] = a<b?[a,b]:[b,a]
//2,3,4,6,8
if(k<2||k==5||k==7) {
    console.log(0)
}else {
    if(k==2) {
        console.log(String(4n*a*a))
    }else if(k==3) {
        console.log(String(a*(b-a)*8n))
    }else if(k==4) {
        console.log(String(4n*(b-a)*(b-a)+a*2n*(N+M-4n*b)))
    }else if(k==6) {
        console.log(String((b-a)*2n*(N+M-4n*b)))
    }else if(k==8) {
        console.log(String((N-2n*b)*(M-2n*b)))
    }
}

여담으로, 필자가 기여하기 전까지 Unrated 되어 있던 문제였다. 각 $k$에 맞는 식을 찾는 것보다 어떤 상황에서도 항상 적용되는지 증명하는 게 더 어려웠던 문제이지만, 별다른 코딩 지식이 없어도 풀 수 있기 때문에 난이도는 실버5로 책정했다.