[BOJ/백준] 10836 여왕벌 파이썬

문제 링크 : https://www.acmicpc.net/problem/10836

10836번: 여왕벌

 

처음에는 그날그날 모든 칸의 크기를 구해서 넣어줬다. 그랬더니 시간이 너무 오래 걸려서 다시 생각해봤다.

모든 애벌래는 1부터 시작하고 첫번째 행, 첫번째 열을 제외하고는 그칸에서 왼쪽, 오른쪽, 왼쪽위칸의 값중 가장 큰값이 해당 칸의 크기가 된다.

그렇기 때문에 그냥 첫행, 첫열의 값만 구해주면 된다.

 

입력으로 들어온 값은 애벌레들이 자라는 정도를 왼쪽 제일 아래 칸에서 시작하여 위쪽으로 가면서 읽고 제일 위쪽 칸에 도착하면 오른쪽으로 가면서 행의 끝까지 읽었었을 때 자라는 크기를 기록한 값으로 +0,+1,+2의 개수이다.

 

이를 a,b,c라고 했을 때

0~a-1번째는 +0만큼

a~a+b-1까지 +1

a+b~끝까지는 +2가 된다는 것이다.

 

2 3

1 1 1

0 3 0

0 0 3

 

입력 예제1로 계산하면 아래처럼 될 것이다.

첫날 1 1 1 들어옴

0~0 : +0

1~1 : +1

3~끝 : +2

1 1 1 -> 1 2 3

둘째날 0 3 0 들어옴

0~-1 : +0 (-1이므로 없다는 것)

0~ 2: +1

3~끝: +2

1 2 3 -> 2 3 4

셋째날 0 0 3 들어옴

0~-1: +0

0~-1: +0

0~끝: +2

2 3 4 -> 4 5 6

 

4 5 6 이 바깥쪽 벌레들의 크기가 된다. 자라는 크기는 감소하지 않는다고 했으므로 벌레들의 크기는 크기가 증가하도록 계산이 될 것이다.

그리고 이를 배열에 넣는 다면

5 6

4 1

이 될 것이다.

 

이제 나머지 안쪽 1의 값은 첫 행의 두번째번부터 마지막 값까지 똑같이 들어가게된다.

문제에 입력에 보면 애벌래가 자라는 크기는 감소하지 않는 다고 했으므로 

왜냐면 현재 칸은 왼쪽, 위, 왼쪽위 칸중 가장 큰값이 들어가기 때문에 결국 첫행의 값이 가장 큰 값이 된다.

그래서 답은

5 6

4 6

이 된다.

 

설명은 똥같지만 코드를 보면 금방 이해가 될 것이다.

 

from sys import stdin

input = stdin.readline
m,n = map(int, input().split())

def solv():
    worm = [1]*(2*m-1)
    for _ in range(n):
        a,b,c = map(int, input().split())
        for idx in range(a,a+b):
            worm[idx] += 1
        for idx in range(a+b,2*m-1):
            worm[idx] += 2

    for idx in range(m-1,-1,-1):
        print(*([worm[idx]]+worm[m:]))
solv()