[알고리즘][python] 백준 1022

문제 링크

백준 1022

문제 풀이

출력의 시작점(r1, c1)부터 출력의 끝점(r2, c2)까지 2중 for문을 돌린다.

for문이 한번 돌때마다 지금 for문의 지점(rx, cx)과 원점과의 관계를 수학적으로 계산한다.

크게 설명하자면, 원점(소용돌이의 시작점)은 1이 써있고, 그 밖을 감싸고 있는 8개의 숫자는 2~9까지다. 또 그밖을 감싸고 있는 16개의 숫자는 10~25이다. 1, 2~9, 10~25 이걸 하나의 껍질이라 생각하자. 1은 첫번째 껍질, 2~9는 두번째 껍질, 10~25는 세번째 껍질...

이때, (rx, cx)가 몇번째 껍질에 있는지 수학적으로 계산한다. 이 계산은 rx의 절대값과 cx의 절대값을 비교해서 큰 값을 (큰 값+1)껍질이라 할 수 있다. (예를 들어, rx=-3, cx=2일때, 현재 이 점(rx, cx)는 (3+1)번째 껍질이라고 할 수 있다.

다음으로, 해당 껍질에 속하는 숫자들의 최소값을 계산을 통해 구한다. 첫번째 껍질의 최소값은 1, 두번째 껍질의 최소값은 2, 세번째 껍질의 최소값은 10...이 수들을 나열해 보면 식이 나온다.

마지막으로, 방금 계산한 최소값에서 (rx, cx)까지 소용돌이가 진행하면 얼마나 수가 커지는지 계산한다. 예를들어, 두번째 껍질(2~9)에서 7까지 가려면 최소값 2에서 +5를 해줘야한다. 이도 수학적으로 계산이 가능하다. 힌트를 주자면, i와 j가 양수인지 음수인지의 경우의 수를 따져가면서 계산하면 된다. (밑의 코드에 나와있다.)

출력조건이 까다롭다. 오와 열을 맞춰야 하기 때문에 띄어쓰기를 해줘야한다. 파이썬에선 rjust함수로 이쁘게 출력이 가능하다.

내 코드(더럽다.)

import sys
import math
from queue import PriorityQueue

r1, c1, r2, c2 = map(int, sys.stdin.readline().split())

answer = []
max:int = 0
for i in range(r1, r2 + 1, 1):
    myList = []
    for j in range(c1, c2 + 1, 1):
        num = 0
        if abs(i) > abs(j):
            if i > 0 and j > 0:
                num += abs(i) * 7 + j
            elif i > 0 and j <= 0:
                num += abs(i) * 6 + (abs(i) - abs(j))
            elif i <= 0 and j <= 0:
                num += abs(i) * 3 + abs(j)
            elif i <= 0 and j > 0:
                num += abs(i) * 2 + (abs(i) - abs(j))
            myList.append(8 * ((abs(i) - 1) * (1 + (abs(i) - 1)) / 2) + 1 + num)
            if max < (8 * ((abs(i) - 1) * (1 + (abs(i) - 1)) / 2) + 1 + num):
                max = (8 * ((abs(i) - 1) * (1 + (abs(i) - 1)) / 2) + 1 + num)
            answer.append(((i, j), (8 * ((abs(i) - 1) * (1 + (abs(i) - 1)) / 2) + 1 + num)))
        else:
            if i > 0 and j > 0:
                if i==j:
                    num += abs(j) * 8
                else:
                    num += abs(j) * 0 + (abs(j) - abs(i))
            elif i > 0 and j <= 0:
                num += abs(j) * 5 + i
            elif i <= 0 and j <= 0:
                num += abs(j) * 4 + (abs(j) - abs(i))
            elif i <= 0 and j > 0:
                num += abs(j) * 1 - i
            myList.append(8 * ((abs(j) - 1) * (1 + (abs(j) - 1)) / 2) + 1 + num)
            if max < (8 * ((abs(j) - 1) * (1 + (abs(j) - 1)) / 2) + 1 + num):
                max = (8 * ((abs(j) - 1) * (1 + (abs(j) - 1)) / 2) + 1 + num)
            answer.append(((i, j), (8 * ((abs(j) - 1) * (1 + (abs(j) - 1)) / 2) + 1 + num)))


maxLength = len(str(int(max)))


for i in range(len(answer)):
    print(str(int(answer[i][1])).rjust(maxLength), end='')
    print(' '*(1), end='')
    if(i%(c2-c1+1)==(c2-c1)):
        print('')