[백준] 10836번: 여왕벌 (파이썬/Python) - 시뮬레이션/구현/Greedy

https://www.acmicpc.net/problem/10836

10836번: 여왕벌

for 문 잘못돌리다가 이런 삽질이 발생했다..

 

이 문제는 구현/시뮬레이션 유형이지만 한편으로는 greedy 알고리즘으로 규칙을 찾아야 한다. 

핵심 아이디어는 다음과 같다. 

 왼쪽 아래에서부터 위, 오른쪽 방향으로 성장한 애벌레의 값을 갱신해주는데, 이 화살표 순서대로 숫자가 작아지지 않는다고 했으므로, 
갱신되지 않은 (m-1) * (m-1) 칸들의 값은 자기자신의 바로 윗칸의 값을 가져오면 된다. 

즉 자기자신의 바로 윗칸이 가장 증가한 값이 높은 칸이다. 

import sys
input = sys.stdin.readline

m, n = map(int, input().split())
array = [[1] * m for _ in range(m)]
grow = [0] * (2 * m - 1)  # 성장하는 정도
for _ in range(n):
    a, b, c = map(int, input().split()) # 0, 1, 2
    # grow 배열에 한꺼번에 성장하는 정도를 저장한다.
    for i in range(a, a+b):
        grow[i] += 1
    for i in range(a+b, 2*m-1):
        grow[i] += 2

index = 0
    # 왼쪽 열 채우기
for j in range(m-1, -1, -1):
    array[j][0] += grow[index]
    index += 1

    # 위쪽 행 채우기
for i in range(1, m):
    array[0][i] += grow[index]
    index += 1

# 나머지 칸 채우기
# 모든 입력에서 왼쪽 아래 -> 왼쪽 위 -> 오른쪽 은 감소하지 않으므로, 항상 자기자신의 위칸이 최대 증가
for i in range(1, m):
    for j in range(1, m):
        array[i][j] = array[i-1][j] # 초기값이 1 이므로

# 결과 출력
for i in array:
    print(*i)