10836. 여왕벌 (Python)

10836번: 여왕벌

 

풀이

 입력으로 주어진 M(가로, 세로의 크기)에 맞춰서 M * M 사이즈의 배열을 만들어줄 필요는 없다. 제일 왼쪽 열과 제일 위쪽 행 크기만큼, 즉 2M - 1 크기만큼의 배열을 만들어서 애벌레의 크기를 기록해주면 된다. 그 이유는 다음과 같은 조건 때문이다.

1. 제일 왼쪽 열과, 제일 위쪽 행의 애벌레들은 자신이 자라는 정도를 스스로 결정한다. 이들은 입력으로 주어질 것이다. 애벌레들이 자라는 정도를 왼쪽 제일 아래 칸에서 시작하여 위쪽으로 가면서 읽고, 제일 위쪽 칸에 도착하면 오른쪽으로 가면서 행의 끝까지 읽었다고 하자. 모든 입력에서 이렇게 읽은 값들은 감소하지 않는 형태이다.

 

 나머지 애벌레들은 자신의 왼쪽, 윈쪽 위, 위쪽의 애벌레들 중 가장 많이 자란 애벌레가 자란 만큼 자란다고 하는데 위의 조건에서 굵게 표시된 이유 때문에 항상 자신의 위쪽 애벌레가 커진 만큼 커지게 된다. 

 

 

 위 그림은 M이 4일 때의 그림이다. 적힌 숫자는 2M-1 크기를 가진 배열에서의 인덱스 번호이다. 제일 왼쪽 열과 제일 위쪽 행은 입력으로 주어진 대로 커지지만 나머지 애벌레는 항상 자신의 위쪽 애벌레만큼 커지기 때문에 결국 자신의 위쪽 애벌레와 같은 크기를 가지게 된다.

 그렇기 때문에 모든 애벌레 사이즈를 기록할 필요 없이 2M-1 사이즈의 배열에 애벌레를 기록하고 나머지 애벌레는 자신의 위에 해당하는 인덱스에 기록된 값을 출력해 주면 된다.

 

 

코드

import sys 
input = sys.stdin.readline


if __name__ == '__main__':
    M, N = map(int, input().split())  # M: 가로와 세로 크기, N: 날짜 수
    larva = [1 for _ in range(2*M+1)] # 애벌레의 크기 

    for _ in range(N):
        zero, one, two = map(int, input().split())
        
        for i in range(zero, zero + one): # 애벌레 크기 1만큼 증가
            larva[i] += 1
        
        for i in range(zero+one, zero+one+two): # 애벌레 크기 2만큼 증가
            larva[i] += 2
    
    # 제일 왼쪽 열과, 제일 위쪽 행의 애벌레는 입력으로 주어진 만큼 커진다.
    # 나머지 애벌레는 항상 자신의 위쪽 애벌레만큼 크기가 커지게 된다.
    # 따라서 [i][j] (i >= 1, j >= 1) 위치의 애벌레는 항상 [0][j]의 애벌레의 크기와 같다.
    for i in range(M):
        for j in range(M):
            if j == 0:
                print(larva[M - (i + 1)], end=' ')
            else:
                print(larva[M + j - 1], end=' ')
        print()