백준[10836] 여왕벌 (Python3)

bfs로 풀었다면 시간초과를 받았을 문제
정올 문제답게 관찰이 필요한 문제이다.

문제를 보면 흥미로운 사실을 하나 알 수 있는데
애벌래들의 초기 성장 수치는 오른쪽으로 갈 수록 커진다.
그리고 애벌래들은 왼쪽, 왼쪽 위, 위쪽만 확인한다.

즉, 왼쪽 위보단 위쪽이 위치상으로는 더 오른쪽으로 있기 때문에
그냥 위쪽 값만 보면 된다.
즉, (1, 1)부터 (M, M)까지의 애벌래들은 각각 (0, 1) ~ (0, M)의 애벌래의 성장 수치를 그대로 받는다.

또한, 모든 애벌래의 성장 수치는 첫행, 첫열의 애벌래와 똑같고, 추가로 고려할 사항은 없다.
따라서 첫행, 첫열 애벌래들의 성장 수치를 더한 뒤
나머지 애벌래들은 바로 위쪽 애벌래의 성장 수치 합을 그대로 가져다 쓰면 된다.

 

M, N = map(int, input().split())
board = [1 for _ in range(2 * M - 1)]
for i in range(N):
    nums = list(map(int, input().split()))
    index = 0
    for j in range(3):
        for k in range(nums[j]):
            board[index] += j
            index += 1

half = (2 * M - 1) // 2
A = board[half + 1:]
for i in range(half, -1, -1):
    print(board[i], end= " ")
    for a in A:
        print(a, end= " ")
    print()