[백준 10836번] 여왕벌

문제 링크: 10836번 제목

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

 

입력받은 배열을 일반적인 변수로 두고, 각 칸이 어떤 값을 가지는지 살펴볼 수 있다. 예를 들어, 벌집의 크기가 5라면 다음과 같다.

 

그리고 입력 조건의 "본문에서 보인 것과 같이, 자라는 크기를 제일 왼쪽 아래 칸에서 시작해서 위쪽으로 올라가서 제일 위쪽에 도착하면 오른쪽으로 이동하며 읽었다고 하자. 이 값들은 감소하지 않는다."에 따라서, a < b < c < ... < i를 만족하므로 위 표는 아래와 같다.

 

 

이 때 a, b, c, ..., i는 0, ..., 0, 1, ..., 1, 2, ..., 2와 같은 형태일 것이므로 a, b, c, ..., i 각각에 대해 누적 합이 얼마였는지만 알고 있으면 각각 애벌레가 얼마나 자랐는지를 알 수 있다. 곧 시간복잡도는 O(nm) = 7억이다.