백준 3004 : 체스판 조각

www.acmicpc.net/problem/3004

3004번: 체스판 조각

if __name__=='__main__':
    N = int(input())
    if N==0: ans = 1
    elif N%2 == 0 : ans=(N//2+1)**2
    else : ans = (N//2+1)*(N//2+2)
    print(ans)

N=0일 때가 코너 케이스이다. 

평행하게 자른다고 하였으니, 최대의 조각을 내려면 매번 그 전 방향의 수직으로 잘라야만 한다.

 

증명:

컷팅 N번 중, 세로에 평행하게 n번, 가로에 평행하게 m번 컷팅 했다고 하자. ( N = n+m, n > m )

그러면, 가로에 평행하게 자르면 (n+1) 조각을, 세로에 평행하게 자르면 (m+1) 조각을 추가로 만들 수 있다.

최대의 조각을 만들기 위해서는 가로에 평행하게, 즉, 더 적게 컷팅한 방향으로 컷팅해야 한다.

 

빈 체스판 컷팅을 시작하는 것이므로, 컷팅 횟수(k)는 0부터 시작.

아래와 같이 행동하게 된다.

          k = 1 : 가로(세로) 방향으로 잘랐다 가정 

          k = 2. : 세로(가로) 방향 컷팅 수가 1 적음 --> 세로 방향 컷팅

            ...

k = odd: 가로와 세로 컷팅 횟수가 같다 --> 가로(세로)에 평행하게 컷팅했다 가정.

k = even: 더 적게 컷팅한 방향 = 직전에 컷팅한 수직 방향으로 컷팅해야 함.

 

즉, 홀수번 컷팅 기회가 주어지면, 한 번의 컷팅이 차이 나고,

짝수번 컷팅 기회가 주어지면, 정확히 같은 횟수로 컷팅하게 된다.