반응형
https://www.acmicpc.net/problem/1912
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
내 답안
N = int(input())
x = list(map(int, input().split()))
for i in range(1, N):
x[i] = max(x[i], x[i] + x[i - 1])
print(max(x))
사실 처음에 코드 짤 때는
N = int(input())
x = list(map(int, input().split()))
dp = [0] * N
for i in range(1):
for j in range(i, N):
dp[j] = sum(x[i:j + 1])
for i in range(1, N):
for j in range(i, N):
dp[j] = max(dp[j], sum(x[i:j + 1]))
print(max(dp))
dp 테이블을 처음 만들고 이중 for 문으로 다 계산을 하였다.
하지만 시간 복잡도가 O(N^2)이라 시간 초과가 떴었다.
.
.
그래서 따로 태블릿에 적어 곰곰이 생각을 해보았다.
이중 for 문으로 돌지 않고 그냥 for 문 한 개로도 끝낼 수 있지 않을까?
x[i] = max(x[i], x[i] + x[i - 1])
생각해 보니
이 한 줄 자체가 x[i] 자리를 끝내는 거이기 때문에
for 문 한 줄로도 쉽게 가능한 문제였다.
따라서 이중 for 문을
for 문 한 개로 줄여서 문제를 해결하였다.
for i in range(1, N):
x[i] = max(x[i], x[i] + x[i - 1])
반응형
'BOJ > Python' 카테고리의 다른 글
백준 7785번 회사에 있는 사람 파이썬 (0) | 2022.06.06 |
---|---|
백준 4673번 셀프 넘버 파이썬 (0) | 2022.04.27 |
백준 11399번 ATM 파이썬 (0) | 2022.04.17 |
백준 16953번 A -> B 파이썬 (0) | 2022.04.12 |
백준 1181번 단어 정렬 파이썬 (0) | 2022.04.11 |