글 읽기 - 이문제가 DFS로는 해결이 안되나요?

가로 세로가 300이하인데 DFS의 시간 복잡도가 정확히 어떻게 된다는건지 궁금합니다.

왼쪽, 아래 방향뿐이니 break문을 적절히 섞으면 성공할 것이라 생각했는데 이 문제를 DFS로 해결하는 것은 아에 불가능한지 궁금합니다.

연속해서 1인 구간의 최대가 아니라 중간에 0 이 있어도 최대인 구간을 찾는 문제에요

3 3

1 0 1

0 0 1

위 예제는 4 가 나와야 합니다.

저는 dp 로 해결했습니다.

dfs + 메모이제이션을 활용한 dp를 쓰시면 가능합니다.

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

Baekjoon Online Judge