1. 문제 설명
https://www.acmicpc.net/problem/1022
1022번: 소용돌이 예쁘게 출력하기
첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다.
www.acmicpc.net
정말 기억에 오래 남는 문제다.
이 문제를 풀기 위해서 12시간을 스카에 박혀있다가 결국 해결 못 하고
다음날 12시간을 더 할애했던 문제였었다.
순전히 PyPy로 시간 초과를 극복하는 것은 자존심이 허락하지 않는다는 얼토당토 않는 이유에서였다..
2. 아이디어
이 문제는 풀이 방법이 2가지가 있다. (물론 더 있을 수 있지만, 난 모르겠다.)
하나는 무식하게 진짜 소용돌이를 다 '그려보는 것'이고,
다른 하나는 수학적으로 접근하여 위치를 추적하여 값을 출력하는 것이다.
전자는 당연히 시간초과가 나서 PyPy로 제출해야하고 (C++은 될 수도..? 안 해봐서 모르겠다.)
후자는 위의 사진을 보면 메모리와 시간이 압도적으로 단축됨을 알 수 있다.
주의할 점!
출력 형식이 안 맞는 이유는 글자의 개수까지 체크해서 맞춰줘야 하는 조건 때문이다.
ex)
18 5 4 3 12
19 6 1 2 11
20 7 8 9 10
21 22 23 24 25
이런 느낌으로..? ㅋㅋㅋ 다시 풀기 싫은 문제..
1. 무식하게 풀기
이건 딱히 아이디어랄 것은 없고 구현 문제에 가까운 접근법이다.
정직하게 값을 다 계산하면서 그리다가 유효 범위안에 들어서면 리스트 안에다가 값을 넣어 저장한다.
모눈종이에 그릴 영역의 꼭짓점 절댓값이 가장 작은 좌표를 알아내어, 영역 안에 1이 포함되는가를 파악한다.
이렇게 구분지어주는 이유는 1을 포함하는 영역을 그리면 1부터 시작하고
그게 아니라면 꼭짓점을 포함하는 테두리 기점으로 값을 만들기 시작해야하는데,
구분을 안 하면 1부터 시작해야되는 경우에 난데없이 꼭짓점을 찾고 있는 괴상한 과정을 거치게 된다.
그렇게 시작점을 잡게 되면 while문을 돌리면서 모눈종이에 숫자를 쓸 때마다 size를 1씩 까면서
반복을 돌려주면 된다.
문제는 input값으로 -5000 -5000 -4951 -4996 같은 좌표를 던져주면
노트북 팬 소리가 비행기 이륙하는 소리와 맞먹는 굉음을 낸다.
2. 수학적 접근
이 방법은 모눈종이 안에 들어갈 값을 하나하나 조합해내어 끼워맞춘다고 생각해도 좋다.
우선, 주어진 좌표에서 더 큰 절댓값이 좌표가 어느 테두리에 속하는지를 결정해주는 지배적인 수치가 된다.
예를들어, (-3, 1)은 3번째 테두리에 속하는 좌표이다.
그 다음은 좌표가 몇 사분면에 속해있는지를 판단한다.
간단한 논리이므로 설명은 코드로 대체한다.
다음은 해당 좌표를 포함하고 있는 테두리의 각 꼭짓점의 값을 알아낸다.
우측하단의 값이 1, 9, 25, 49, ...로 증가하므로 점화식은 \(a_{n} = a_{n-1} + 8n\)가 된다.
그러면 아래와 같은 데이터를 얻을 수 있다.
여기까지 구했으면 몇 사분면인지에 따라 조건을 나누어서
꼭짓점의 값을 통해 원하는 좌표의 값을 구하면 끝이 난다.
3. 코드
1. 시간초과 나는 풀이
def solution():
r1, c1, r2, c2 = map(int, input().split())
board = [[0]*(c2 - c1 + 1) for _ in range(r2 - r1 + 1)]
size = (c2 - c1 + 1) * (r2 - r1 + 1)
move_row, move_col = [0, -1, 0, 1], [1, 0, -1, 0]
outermost = min(abs(r1), abs(c1), abs(r2), abs(c2))
cnt = 0
if outermost == 0 or outermost - 1 == 0 or (r1 < 0 < r2 and c1 < 0 < c2):
num = 0
row, col = 0, 0
limit, tmp = 1, 0
else:
num = 1
for position in range(1, outermost, 1):
num += 8 * position
row, col = outermost - 1, outermost
limit, tmp = 2 * outermost - 1, 1
while size > 0:
cnt += 1
num += 1
if r1 <= row <= r2 and c1 <= col <= c2:
board[row - r1][col - c1] = num
size -= 1
row += move_row[tmp]
col += move_col[tmp]
if cnt == limit:
cnt = 0
if tmp == 1 or tmp == 3:
limit += 1
tmp = (tmp + 1) % 4
max_length = 0
for i in range(len(board)):
for j in range(len(board[i])):
max_length = max(max_length, len(str(board[i][j])))
for i in range(len(board)):
for j in range(len(board[i])):
print("{:>{}}".format(str(board[i][j]), max_length), end = ' ')
print()
solution()
2. 수학적 연산이 감미된 풀이
r1, c1, r2, c2 = map(int, input().split())
board = [[0]*(c2 - c1 + 1) for _ in range(r2 - r1 + 1)] # 최종 출력 리스트
max_length = 0 # 가장 큰 숫자 길이
def check_quadrant(row, col):
if row > 0 and col >= 0: # 4사분면
return 4
if row >= 0 and col <= 0: # 3사분면
return 3
if row <= 0 and col <= 0: # 2사분면
return 2
if row <= 0 and col >= 0: # 1사분면
return 1
def get_value_vertex(outermost):
tmp = []
num = 1
for position in range(1, outermost + 1, 1):
num += 8 * position
for i in range(4):
tmp.append(num - (2 * outermost * i)) # 해당 영역의 각 꼭짓점 값 도출
return tmp
def fill_board(row, col):
global max_length
outermost = max(abs(row), abs(col)) # 영역의 위치를 지배하는 좌표로 확인
quadrant = check_quadrant(row, col) # 해당 row, col 좌표가 몇 사분면에 위치하는가?
vertex = get_value_vertex(outermost)
if quadrant == 1:
if outermost == abs(row):
temp = outermost - abs(col)
value = vertex[3] + temp
else:
temp = outermost - abs(row)
value = vertex[3] - temp
elif quadrant == 2:
if outermost == abs(row):
temp = outermost - abs(col)
value = vertex[2] - temp
else:
temp = outermost - abs(row)
value = vertex[2] + temp
elif quadrant == 3:
if outermost == abs(row):
temp = outermost - abs(col)
value = vertex[1] + temp
else:
temp = outermost - abs(row)
value = vertex[1] - temp
else:
if outermost == abs(row):
temp = outermost - abs(col)
value = vertex[0] - temp
else:
temp = outermost - abs(row)
value = vertex[3] - 2 * outermost + temp
max_length = max(max_length, value)
return value
def solution():
global max_length
for row in range(r2 - r1 + 1):
for col in range(c2 - c1 + 1):
board[row][col] = fill_board(r1 + row, c1 + col)
for i in range(len(board)):
for j in range(len(board[i])):
print("{:>{}}".format(str(board[i][j]), len(str(max_length))), end = ' ')
print()
solution()