1912번 - 연속합
동적계획법을 이용해 각 입력의 연속합을 모두 기록하고, 그중 최댓값을 취하는 방식으로 코드를 짜봤는데요..
시간초과가 나네요.. for 중첩을 줄일 수 있는 방법이 있을까요?
DP[i] = (i번째 수를 구간의 마지막으로 하는 최대 연속구간합)
으로 정의하면
DP[i] = (?)
한 번 생각해보세요! 하실 수 있을 겁니다
특별히 배열에 값을 저장안하시고 변수 두개로만으로도 충분히 답을 만들 수 있습니다.
1. 수를 입력받는다.
2. 수의 합을 구해서 그 값이 음수면 그 수부터 다시 계산 시작, 그렇지 않으면 합을 계산
3. 합의 최댓값을 만든다.
4. 최댓값이 답
덕분에 잘 해결했습니다!
감사합니다!
댓글을 작성하려면 로그인해야 합니다.
furyhunter 7년 전
동적계획법을 이용해 각 입력의 연속합을 모두 기록하고, 그중 최댓값을 취하는 방식으로 코드를 짜봤는데요..
시간초과가 나네요.. for 중첩을 줄일 수 있는 방법이 있을까요?