[백준 13437] 슈퍼 나이트

티어: 실3

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

 

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

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

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

 

k=0

움직일 수 있는 칸이 없는 위치가 존재하려면, 2*a>M 을 만족해야한다. 당연하게도 조건에 의해 이런 테스트케이스는 존재하지 않는다. 따라서 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*a*a 를 출력하면 된다.

 

k=3

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

 

k=4

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

 

k=6

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

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

 

k=8

임의의 칸을 기준으로 상하좌우 모두 2b칸 만큼의 여유가 있다면 k=8 이라고 할 수 있다. 반대로 생각하면, 이걸 만족하는 칸은 (N-2b)(M-2b)개가 있다는 뜻이다. 따라서 (N-2*b)(M-2*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로 책정했다. +2025/04/15: 과정이 실버5보단 많이 어려웠던듯.. 실버3으로 조정했다.