[Python] 백준(BOJ) 10157번: 자리배정 - 달팽이 수열

문제

10157번: 자리배정

풀이

이번 시즌 풀었던 코테문제와 상당히 유사했던 문제 (미리 풀어볼걸)

이 문제는 달팽이수열의 기본적인 문제인데, 달팽이 수열이란 순서대로 빙글빙글 돌며 채운 행렬을 뜻한다.

1~6까지 위 방향 (R-0개)

7~12까지 오른쪽 방향 (C-1개)

13~17까지 아래 방향 (R-1개)

18~22까지 왼쪽 방향 (C-2개)

23~26까지 위 방향 (R-2개)

...

이런식으로 반복되는 규칙을 갖고 있다.

R, C가 순서대로 반복되고, i가 2번에 1씩 증가한다.

 

문제에서는 인풋으로 받는 숫자 K의 좌표를 리턴해야했다. 

먼저 처음 한번을 제외하고는 R-i, C-i에서 i가 2번씩 쓰이기 때문에 K가 R보다 작거나 큰 경우와, 

K가 R * C 의 범위를 벗어난 경우에도 예외 처리를 해줬다.

 

그 후에는 포문으로 계속 돌리면 시간초과가 날 것 같아서 각 모서리를 찾기위해 규칙을 찾아 더해줬다. 

(예. 11을 찾아야하면 그 라인의 모서리인 12찾은 후 왼쪽으로 1 가기 (12의 좌표에서 x좌표 -1 해주기))

 

cur_num는 모서리값을 저장했고

c는 boolean 타입으로 c차례인지, r차례인지

rev는 -1 or 1로 (위/오른쪽)인지 (아래/왼쪽)인지를 판단했다. 

코드 정리를 안해서 코드가 좀 더럽긴 하지만.. 해결완료!

 

import sys

C, R = map(int, sys.stdin.readline().split(" "))

K = int(sys.stdin.readline())

if K > C * R:
    print(0)
elif K <= R:
    print(1, K)
else:
    cur_num = R
    cur_coord = [1, R]
    index = 1
    c = True
    rev = 1
    reverse = True
    while cur_num < K:
        if c:
            cur_num += (C - index)
            cur_coord = [cur_coord[0] + rev * (C - index), cur_coord[1]]
            rev *= -1
            c = False
        else:
            cur_num += (R - index)
            c = True
            cur_coord = [cur_coord[0], cur_coord[1] + rev * (R - index)]
            index += 1
            reverse = not reverse

    if cur_num == K:
        print(cur_coord[0], cur_coord[1])
    else:
        diff = K - cur_num
        if c:
            if reverse:
                cur_coord = [cur_coord[0], cur_coord[1] + diff]
            else:
                cur_coord = [cur_coord[0], cur_coord[1] - diff]
        else:
            if reverse:
                cur_coord = [cur_coord[0] + diff, cur_coord[1]]
            else:
                cur_coord = [cur_coord[0] - diff, cur_coord[1]]

        print(cur_coord[0], cur_coord[1])