[백준] 1912번 - 연속합

1. 연속합

• 난이도
  • 실버 2
• 시간 제한
  • 1초
• 메모리 제한
  • 128 MB
• 출처
  • 1912번: 연속합 (acmicpc.net)

A. 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

B. 내 답안

a. 1차 제출 (틀림)

n = int(input())  
array = list(map(int, input().split()))  
answer = -1001  
  
for i in range(len(array)):  
    for j in range(0, len(array)):#, i+1):  
 start = j  
        end = j + i+1  
 answer.append(sum(array[start:end]))  
        # print(answer)  
  
print(max(answer))

b. 2차 제출 (틀림)

n = int(input())  
array = list(map(int, input().split()))  
answer = -1001  
  
A = sorted(array, reverse=True)  
B = []  
# print(A)  
for i in A:  
    B.append(array.index(i))  
  
# print(B)  
big = B[0]  
start = 0  
end = len(B)-1  
for i in range(len(B)):  
    if B[i] <= B[0]:  
        answer = max(answer, (sum(array[B[i]:B[0]+1])))  
        start = i  
    else:  
        answer = max(answer, (sum(array[B[0]:B[i]+1])))  
        end = i  
    answer = max(answer, sum(array[B[start]:B[end]+1]))  
  
print(answer)

c. 3차 제출 (틀림)

n = int(input())  
array = list(map(int, input().split()))  

answer = []  
answer.append(sum(array))  
  
for i in range(len(array)-1):  
    if array[0] >= array[-1]:  
        array.pop()  
    elif array[0] < array[-1]:  
        array.pop(0)  
    answer.append(max(answer[-1], sum(array)))  
  
print(max(answer))

d. 4차 제출 (통과)

n = int(input())  
array = list(map(int, input().split()))  

answer = []  
answer.append(array[0])  
for i in range(1, n):  
    answer.append(max(answer[i-1]+array[i], array[i]))  
  
print(max(answer))

a. 회고

풀이

예시를 풀어보면 아래 그림처럼 나온다.

하지만 기술한 연산들을 전부 수행하기에는 불필요한 시간이 많이 소요된다. 그래서 아래 그림처럼 불필요한 연산을 제거할 수 있다.

하지 않아도 되는 연산을 제외하고 연속된 두 수의 합을 구하여 더 큰 수를 선택하면 해결할 수 있다.

반성

맞다고 확신한 방식이 틀렸을때, 어떻게 해야할지를 몰랐었다. 이건 뭐 더 연습해야지, 어쩔 수 없다.

결론

• 아직도 c번이 통과하지 못하는 이유가 뭔지 잘 모르겠다. 전체합에서 리스트의 맨 앞과 맨 뒤 수 중 작은 수를 제외한 나머지 전체 합이 이전 전체 합보다 크냐 작냐를 보는 건데.. 왜 안되는걸까.

참고문헌

1912번: 연속합 (acmicpc.net). Baekjoon. (accessed Sep 5, 2021)

#코딩테스트 #알고리즘 #문제 #파이썬 #백준 #다이나믹프로그래밍