[백준 10836] 여왕벌 - Python

문제 보기

[사용한 알고리즘]

구현

 

[문제 접근]

애벌레가 자라는 날짜 한 줄마다 정보를 업데이트하면 시간 초과가 발생하였다. 따라서 애벌레가 각 날마다 자라는 정도를 모두 더한 후 한 번에 처리하였습니다.  

 

[알고리즘]

1. 각 날마다 애벌레가 자라는 정도를 모두 더해서 저장합니다.

2. 나머지 애벌레들의 자라는 정도를 계산합니다.

 

* 제일 왼쪽 아래 칸에서 시작해서 위쪽으로 올라가서 제일 오른쪽에 도착하는 애벌레 증가 정보는 감소하지 않으므로 현재 칸에서 0행에 있는 값 - 1 만큼 현재 칸의 애벌레 크기를 증가시키면 됩니다.

 

[코드]

import sys


def around_grow(array):
    for i in range(1, m):
        for j in range(1, m):
            array[i][j] += array[0][j] - 1


def grow(array, grow_array):  # g 배열을 활용하여 애벌래 크기 증가
    cnt = 0
    for j in range(m - 1, -1, -1):
        array[j][0] += grow_array[cnt]
        cnt += 1
    for j in range(1, m):
        array[0][j] += grow_array[cnt]
        cnt += 1


if __name__ == "__main__":
    m, n = map(int, sys.stdin.readline().split())
    array = [[1] * m for _ in range(m)]
    # 애벌래 초기 배열 선언
    grow_array = [0] * (2 * m - 1)
    for _ in range(n):
        a, b, c = map(int, sys.stdin.readline().split())
        for i in range(a, a + b):
            grow_array[i] += 1
        for i in range(a + b, 2 * m - 1):
            grow_array[i] += 2

    grow(array, grow_array)
    around_grow(array)

    for i in range(m):
        print(" ".join(map(str, array[i])))