사용자 도구

사이트 도구


ps:problems:boj:2041

숫자채우기

ps
링크acmicpc.net/…
출처BOJ
문제 번호2041
문제명숫자채우기
레벨다이아몬드 5
분류

애드혹

시간복잡도O(nm)
인풋사이즈n<=1000, m<=1000
사용한 언어Python
제출기록30860KB / 556ms
최고기록556ms
해결날짜2022/03/04

풀이

  • 발상:★★★, 구현:★★★
  • 퍼즐 문제에 가까운, 순수 아이디어 문제
  • 전체 그리드에서 아무 2×2 영역을 잡았을때, 값이 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()

토론

댓글을 입력하세요:
H H Y I​ Z
 
ps/problems/boj/2041.txt · 마지막으로 수정됨: 2022/03/16 05:32 저자 teferi