백준 10836. 여왕벌

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

10836번: 여왕벌

 

이 문제 ... 결국 4번 서브태스크의 시간초과를 해결할 방법이 생각나지 않아 다른 분들 코드를 봤다.

그런데 다른 분들 코드를 봐도 이게 왜 시간초과가 아닌지 아직도 이해할수가 없다 ..

 

이 문제를 시간초과 없이 통과하는 방법은 일단 첫행, 첫열을 제외한 곳은 첫 행의 값과 같다는 것을 이해해야 한다. 

문제의 입력 조건을 보면 다음과 같은 말이 있다.

 

자라는 크기를 제일 왼쪽 아래 칸에서 시작해서 위쪽으로 올라가서 제일 위쪽에 도착하면 오른쪽으로 이동하며 읽었다고 하자. 이 값들은 감소하지 않는다

 

이말은 즉 0열과 0행의 값들이 순차적으로 커지는 것이기 때문에,

0열의 값이 0행의 값보다 클 가능성은 없고, 

따라서 0열을 제외한 값들은 0행의 값과 같을수 밖에 없다.

 

그런데 내가 막힌 부분은 이것이 아니다 ..

이렇게 한다고 치더라도 내가 생각했을때 시간복잡도는 O(일의 최대 수 * 3 * 2M) = O(1000000 * 3 * 1400) = O(42억)이 나오는데 통과된다.