글 읽기 - 반례 찾아주세요 ㅠㅠ

nasmik419 2년 전 0

dp(?)로 풀었어요...

num = input()
list = []
ans = []
tmp = input().split(" ")
for i in range(int(num)):
    list.append(int(tmp[i]))
ans.append(list[0])
for i in range(1, int(num)):
    if list[i] + ans[i - 1] >= 0:
        ans.append(list[i] + ans[i - 1])
    else:
        ans.append(list[i])
ans.sort(reverse=True)
print(ans[0])

dldyddlwl 2년 전 3

정말 잘하셨습니다! 그런데 말입니다, 아래를 봐주세요!

for i in range(1, int(num)):
    if list[i] + ans[i - 1] >= 0:        # 0 이상이라면 무조건 선택해도 될까요?
        ans.append(list[i] + ans[i - 1]) # 예를 들어봅시다, 기존의 합(i-1까지의 최대연속합), ans[i-1] 과
                                         # 새로운 원소, list[i] 간의 합에 대한 것입니다.
            
                                  # 이전까지의 최대합(ans[i-1])이 -1이고, 새로운 원소가 5 (list[i])라고 해봅시다.
                                 # 둘의 합은 -1 + 5 = 4 이므로 0 이상입니다.
                                # 하지만, 굳이 기존의 합 -1을 유지할 필요가 없습니다! 오히려 마이너스 합은 버리는 게
                                # 이득입니다. 따라서, 기존 합을 버리고 새로운 원소 5를 고르는 게 최적의 답입니다!
                                #  -1 + 5 = 4 < 5
                            
                              # 따라서, 더 적합한 식은, 기존합 + 새로운 원소 >= 새로운 원소, 
                              # 새로운 원소를 더한 결과가 새로운 원소보다 크거나 같다면 합을 계속 이어가도 된다는 뜻입니다! 
                              # 그렇지 않다면 (else), 합을 버리고 새로 시작하는 겁니다.
                                # list[i] + ans[i-1] >= list[i] , 다시 써보면
                                # ans[i-1] >= 0 입니다. 즉, 기존의 합이 양수여야 이어나갈 가치가 있다는 것이죠!                                    

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

문제

문제

출처

ICPC

반례 찾아주세요 ㅠㅠ

nasmik419 2년 전 0

dldyddlwl 2년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말