[백준]10836 여왕벌 #그리디#격자

1. 풀이

제일왼쪽열, 제일 위쪽 행의 값이 주어지고, 다른 자리는 왼,왼위,위 중 가장 큰 수가 들어오면 되는 조건을 보면 아래와 같은 점화식이 만들어진다.

L[i][j]=max(L[i-1][j],L[i-1][j-1],L[i][j-1])

위의 점화식을 만든것 만으로 뭔가 대단한걸 생각해낸 것 같아서 정답인줄 알았지만 시간초과이다. (N=1,000,000)

 

핵심은 주어지는 왼쪽열, 위쪽행의 값들이 순차적으로 커진다는 것이다. 즉 점화식의 결과는 반드시 아래와 같아진다는 것이다.

max(L[i-1][j],L[i-1][j-1],L[i][j-1])=L[i-1][j]

그러니까 0열을 제외한, 즉 1열보다 뒤에 있는 모든 행들은 0행의 값들을 그대로 받을 수 밖에 없다.

 

따라서 0열과 0행을 다 누적해서 더해주고, 1행부터 밑에값들은 0행과 똑같은 값을 가지게 하면 끝

2. 소스코드

import sys

M,N=map(int,input().split())

L=[[1 for j in range(M)] for i in range(M)]
day=[0 for i in range(2*M-1)]



for _ in range(N):
    z,o,t=map(int,sys.stdin.readline().rstrip().split())
    for i in range(z,z+o):
        day[i]+=1
    for i in range(z+o,2*M-1):
        day[i]+=2

#왼쪽꺼
for i in range(M-1,-1,-1):
    L[i][0]+=day[M-1-i]
#위쪽
for j in range(1,M):
    L[0][j]+=day[M-1+j]

#1열 이후라인
for j in range(1,M):
    for i in range(1,M):
        L[i][j]=L[i-1][j]

for i in L:
    print(*i)