[BOJ_Gold 3] - 1959 달팽이 3 [python]

 

문제

M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다.

ㅇ

위의 그림은 M=5, N=3의 예이다. 이제 표의 왼쪽 위 칸(○)에서 시작하여, 오른쪽으로 선을 그려 나간다. 표의 바깥 또는 이미 그려진 칸에 닿아서 더 이상 이동할 수 없게 되면, 시계방향으로 선을 꺾어서 그려나간다.

ㅇ	→	↘
↗	↘	↓
↑	↓	↓
↑	끝	↓
↖	←	↙

위의 표는 선을 그려 나간 모양을 나타낸 것이다. 선이 꺾어진 부분은 대각선으로 나타내었다.  표의 모든 칸이 채워질 때까지 선을 몇 번 꺾게 될까? 또, 어디에서 끝나게 될까?

입력

첫째 줄에 M과 N이 빈 칸을 사이에 두고 주어진다. (2 ≤ M, N ≤ 2,100,000,000)

출력

첫째 줄에 표의 모든 칸이 채워질 때까지 선이 꺾어지는 횟수를 출력한다. 둘째 줄에 끝나는 점의 좌표를 출력한다. 왼쪽 위 칸의 좌표를 (1, 1), 오른쪽 아래 칸의 좌표를 (M, N)이라고 하자.

---

문제를 자세히 살펴보면, 화살표가 한 바퀴를 돌때마다

row,col이 각각 2씩 감소하고, x,y가 모두 1증가함을 알 수 있습니다.

그렇다면, n,m > 2에 대해, 문제를 다음과 같이 치환할 수 있습니다.

rotate = min(n,m) + min(n,m) % 2 // 2 - 1 #n,m이 회전 후 적어도 1 이상 남아있게 하는 최대 회전 수
n,m = n - rotate, m - rotate #껍질을 제거하고 난 후의 Base 사각형 영역
x,y = rotate + 1, rotate + 1 #기본 좌표가 1,1이기 때문
이 때, x = row, y = col을 나타냅니다.

 

그렇다면, n,m (1 <= n,m <= 2)에 대해, 모든 경우에 대한 꺾임 횟수와 x,y의 위치를 생각해봅시다.

 

Edge : 총 회전 횟수

i ) n = 1, m = 1 

오른쪽으로 한칸 이동하면 종료입니다. 

x,y = rotate + 1,rotate + 1이 되고, 

Edge = rotate * 4

 

 

ii ) n = 1, m = x(단, x >= 2)

오른쪽으로 x-1칸 이동하면 종료입니다.

x,y = rotate + 1, rotate + 1 + x - 1

Edge = roate * 4

 

iii ) n = x, m = 1 (단, x >= 2)

오른쪽으로 1칸 이동 후 아래로 x-1칸 이동하면 종료입니다. 즉, 꺾임 횟수가 1회 추가됩니다.

x,y = rotate + 1 + x - 1, rotate + 1 

Edge = roate * 4 + 1

 

 

iv ) n = 2, m = x (x >= 2)

오른쪽으로 x-1칸 이동 후 아래로 1칸, 다시 왼쪽으로 x-1칸 이동하면 종료입니다. 즉, 꺾임 횟수가 2회 추가됩니다.

y좌표는 변화가 없고, x좌표만 1 추가됩니다.

 

 

v ) n = x, m = 2 (x >= 3)

오른쪽으로 한칸 이동 후 아래로 x-1칸, 다시 왼쪽으로 1칸, 위로 x-2칸 이동하면 종료입니다. 즉, 꺾임 횟수가 3회 추가됩니다.

y좌표는 변화가 없고, x좌표만 1 증가합니다.

 

위의 정리를 코드로 구현하면 다음과 같습니다.

 

n,m = map(int,input().split())
def lastJudge(n : int, m : int) -> tuple:
    # 크기가 n,m인 직사각형 기준으로
    #현재 xy위치가 끝임

    if m * n == 1: #둘다 1인 경우 계산대로 나옴
        return (0,0,0) #그냥 자기 위치

    elif m == 1:
        return (1, n - 1, 0)  # 아래쪽으로 한번 더 꺾을 수 있음 n만큼

    elif n == 1:
        return (0, 0, m - 1)  # 꺾임은 그대로

    elif n == 2:    #위치는 무조건 2,1
        return (2,1,0)  # 무조건 두번꺾임 (우선순위 높음)

    elif m == 2:
        return (3,1,0)  # 무조건 세번꺾임

rotate = ((min(n,m) + min(n,m)%2) // 2 - 1)
x,y = 1 + rotate,1 + rotate

edge,jx,jy = lastJudge(n - rotate * 2, m - rotate * 2)
print(4 * rotate + edge)
print(1 + rotate + jx, 1 + rotate + jy)