궤도

문제 풀이 이것도 유명한 동적계획법 문제인데... 그냥 뭐 간단하게 생각해서 이런 수열이 있다고 하자 5, -8, 9, -1, ... 당연히 처음은 0으로 시작할 것이다. 0+5를 해서 5가 나왔고 다음 숫자를 보니 -8이다. 5+(-8) = -3인데, 우리가 0으로 시작했다는 걸 생각하면 굳이 이 -3을 안고갈 이유는 없다. 그래서 여기서 연결을 끊고 다시 0부터 시작한다. 0+9를 해서 9가 나왔고, 그 다음이 -1이지만 9에서 -1을 더해도 8이고, 뭐 그 뒤에 10이 나올 수도 있는거니까 연결을 끊지않고 계속 이어나간다. 간단히 말하자면 연속합이 음수가 되는순간 연결을 끊고 다시 시작하는 것이다. 다만 모든 입력이 음수인 경우가 있을 수 있다. 코드를 작성할 때 이 부분을 잊지 말아야 한다. 소스..