1912번 - 연속합
제가 어쩌다 보니 dp를 쓰지 않고 문제를 풀게 됐습니다. 시간 복잡도가 O(n)이 나왔는데 dp를 써서 정석대로 문제를 풀었을 땐 시간 복잡도가 어느 정도 나오나요?
dp를 사용한 풀이 또한 O(N)입니다.
아마 dp 테이블을 사용하지만 않았을 뿐 같은 풀이일것이라고 생각합니다.
kadane's algorithm과 같은 키워드로 검색해보시면 좋을 듯 해요.
댓글을 작성하려면 로그인해야 합니다.
ahwlsdn123 2년 전
제가 어쩌다 보니 dp를 쓰지 않고 문제를 풀게 됐습니다. 시간 복잡도가 O(n)이 나왔는데 dp를 써서 정석대로 문제를 풀었을 땐 시간 복잡도가 어느 정도 나오나요?