1912번 - 연속합
안녕하세요. 파이썬으로 문제를 푸는 과정에서 게시글에 반례를 참고하였는데 해결하지 못해 질문드립니다.
연속된 양수와 음수가 있다면 그 값을 더해 dp[]에 저장하여 음수와 양수가 번갈아 나타나는 배열을 하나 만들었습니다.
dp[]이 앞에서 차례대로 더해나가면서 그 값이 dp[]의 최댓값보다 큰 경우에 배열에 추가하는 코드를 작성하였습니다.
만약 더한 누적 값이 0이 되면 0으로 초기화 후에 다음 값부터 이어서 더하게 작성하였습니다.
시간복잡도는 O(N)이 소요되는 건 지 궁금하고 반례를 찾아주시면 코드 수정해보겠습니다.
알고리즘 공부는 처음이라 접근이 이상하거나 더 좋은 접근이 있으면 조언 부탁드립니다!
반례 찾는게 좀 힘들었습니다.
코드 이해가 아직 부족하여 시간복잡도는 모르겠습니다... 화이팅하세요.
아! 감사합니다.
덕분에 빠르게 해결했어요!
0을 무시하게 코드를 작성하여 예외가 많이 발생했네요 :)
dp[]에 음수만 존재하거나 빈 리스트인 경우, max(lst)를 출력하게 만들어 해결하였습니다.
댓글을 작성하려면 로그인해야 합니다.
kizkiz12 1년 전
안녕하세요. 파이썬으로 문제를 푸는 과정에서 게시글에 반례를 참고하였는데 해결하지 못해 질문드립니다.
연속된 양수와 음수가 있다면 그 값을 더해 dp[]에 저장하여 음수와 양수가 번갈아 나타나는 배열을 하나 만들었습니다.
dp[]이 앞에서 차례대로 더해나가면서 그 값이 dp[]의 최댓값보다 큰 경우에 배열에 추가하는 코드를 작성하였습니다.
만약 더한 누적 값이 0이 되면 0으로 초기화 후에 다음 값부터 이어서 더하게 작성하였습니다.
시간복잡도는 O(N)이 소요되는 건 지 궁금하고 반례를 찾아주시면 코드 수정해보겠습니다.
알고리즘 공부는 처음이라 접근이 이상하거나 더 좋은 접근이 있으면 조언 부탁드립니다!