====== 숫자채우기 ======
===== 풀이 =====
* 발상:★★★, 구현:★★★
* 퍼즐 문제에 가까운, 순수 아이디어 문제
* 전체 그리드에서 아무 2x2 영역을 잡았을때, 값이 W, X, Y, Z 이고 차이들이 a,b,c,d라고 해보자. 아래 그림 참고
*
W a X
b c
Y d Z
* X-W=a, Y-W=b, Z-X=c, Z-Y=d
* 이게 만족되게 하려면 a+c=b+d 또는 a-b=d-c 만 성립하면 된다. 모든 2*2 영역에 대해서 이게 만족하도록 값을 채우면 된다.
* 이것을 만족시키는 방법은 워낙 다양하겠지만.. 그렇다고 아무렇게나 하면 답이 안되는 경우도 생긴다.
* 이리저리 고민끝에 떠오른 방법은, |a-b|를 1로 유지하는 것이다. 그러면 대각선 방향으로 1부터 순서대로 채우는 것으로 모든 대각선의 차를 1로 만들어서 저 조건을 성립시킬수가 있다. 다음과 같은 그림이다
*
? 1 ? 6 ? 7 ?
2 5 8 18
? 4 ? 9 ? 17 ?
3 10 16 19
? 11 ? 15 ? 20 ?
12 14 21 24
? 13 ? 22 ? 23 ?
* 이런 방식도 가능하다
*
? 1 ? -3 ? 7 ?
2 -4 8 -13
? -5 ? 9 ? -14 ?
-6 10 -15 19
? 11 ? -16 ? 20 ?
12 -17 21 -23
? -18 ? 22 ? -24 ?
* 이제 공식을 찾았으니 이대로 채우도록 구현만 하면 된다. O(nm)에 n*m 그리드를 채울수 있다.
* 하지만.. 구현이 꽤 복잡했다.. 그리드에 ? 값을 바로 채워나가려고 했는데, 헷갈리는 부분이 많아서 구현에 꽤나 시간을 쏟았다;; 애초에 차이를 먼저 테이블에 저장해놓고 그것을 이용해서 ?값을 채우는 식으로 계산했으면 간단했을텐데.. 그렇게 안해도 쉽게 구현할수 있으리라 생각했다가 꽤 고생했다.
* 차이에 +와 -가 섞여있는 방식으로 구현했는데, 이때에는 초기값에 해당하는 맨 왼쪽 위칸의 값을 그냥 1로 주면 안된다. 중간에 1보다 작은 값이 생길수 있기 때문에 틀리게된다. 넉넉하게 N*M 으로 시작하면 그런 일이 생기지 않는다.
* 제출후에 다른 사람들의 답안을 보니, 다음과 같이 채우는 것도 가능하다는 것을 알았다.
*
? 1 ? -2 ? 3 ?
4 -5 6 -7
? -8 ? 9 ? -10 ?
-11 12 -13 14
? 15 ? -16 ? -17 ?
18 -19 20 -21
? -22 ? 23 ? -24 ?
* 어차피 시간 복잡도는 똑같지만, 이 방법은 칸을 대각선 방향이 아닌 그냥 행->열 순으로 채우면 되기 때문에 구현이 훨씬 간단했다.. 실행 속도도 더 빨랐다.
===== 코드 =====
==== 코드 - 1 (대각 방향) ====
"""Solution code for "BOJ 2041. 숫자채우기".
- Problem link: https://www.acmicpc.net/problem/2041
- Solution link: http://www.teferi.net/ps/problems/boj/2041
Tags: [Ad Hoc]
"""
def main():
N, M = [int(x) for x in input().split()]
answer = [[None] * M for _ in range(N)]
sign = 1
p = 0
answer[0][0] = N * M
for i in range(1, N + M - 1):
sign *= -1
first, last = max(0, i - M + 1), min(N - 1, i) + 1
for j in range(first, last):
p += 2 if j > 0 and i - j > 0 else 1
if i - j == 0:
answer[j][i - j] = answer[i - 1][i - j] + p * sign
else:
answer[j][i - j] = answer[j][i - j - 1] + p * sign
for row in answer:
print(*row)
if __name__ == '__main__':
main()
==== 코드 - 2 (가로 방향) ====
"""Solution code for "BOJ 2041. 숫자채우기".
- Problem link: https://www.acmicpc.net/problem/2041
- Solution link: http://www.teferi.net/ps/problems/boj/2041
Tags: [Ad Hoc]
"""
import itertools
def main():
N, M = [int(x) for x in input().split()]
left_num = N * M
for diff, sign in zip(range(1, 1 + N * (M * 2 - 1), M * 2 - 1),
itertools.cycle([1, -1])):
sign_iter = itertools.cycle([sign, -sign])
v = left_num
row = [v] + [(v := v + x * s)
for x, s in zip(range(diff, diff + M - 1), sign_iter)]
print(*row)
left_num += (diff + M - 1) * sign
if __name__ == '__main__':
main()