neoxenesis   2년 전

이틀째 도전중인데 미칠거같습니다..

코드는 이렇게 짰습니다.

 R,C를 입력받고 그 값에 따라 가능한 최대 다이아몬드의 크기부터 구한 뒤, 그 최대 크기부터 '검사 가능한 좌표만' 하나씩 검사합니다.

예를 들어 다이아몬드 크기가 최대일때는 광산을 꽉꽉 채울때이므로 구하는 경우가 그리 크기 않습니다


그래서 다이아몬드 크기가 최대일때부터 크기를 하나씩 감소시켜서 검사하는데 크기를 감소시킬때마다 검사 가능한 좌표가 제곱으로 늘어납니다

따라서 시간복잡도는 1+4+9+...+n^2꼴이 됩니다

이래서 시간초과가 뜨는걸까요? 구글링해서 다른 분들의 답을 봐도 3중for문 쓰는분들이 대부분이었고 그래서 딱히 시간초과가 될거같지는 않았습니다

가장 최악의 케이스인 R,C가 750이고 전부 0으로 채워있는 상황을 입력해봐도 바로 출력이 나오는데 뭐가 문젤까요???

아니면 여기서 더 줄일 방법이 없을까요.. 백준 시작한지 얼마 안됐고 대학 1학년이라 프로그래밍도 아직 응애라 나름 힘들게 짰는데 너무 허무하네요 ㅠㅠ

flappybird   2년 전

의도된 풀이는 O(N2)만에 동작합니다. 다른 방법을 생각해보세요

3중 포문으로 맞은 답안이 있다니 신기하네요

neoxenesis   2년 전

크아아악 알겠습니다 피드백 감사합니다 :)

레어닉이시네요

댓글을 작성하려면 로그인해야 합니다.