이 문제는 증가하는 부분 수열 중에서 ‘합이 가장 큰 경우’를 찾는 DP 문제이다.
LIS(가장 긴 증가 부분 수열)와 비슷하지만, 길이가 아닌 “부분 수열 값들의 총합”을 기준으로 한다는 점이 핵심이다.
이전에 풀었던 비슷한 유형의 문제 :
11053. 가장 긴 증가하는 부분 수열 (DP) 🥈2️⃣
🧩 문제
수열이 주어졌을 때,
증가하는 부분 수열 중 합이 가장 큰 값을 구하기.
예를 들어
10 30 10 20 20 50 이라면,
가능한 증가 부분 수열 중 합이 가장 큰 건
10 + 20 + 50 = 80 또는 10 + 30 + 50 = 90
→ 답은 90
✏️ 나의 알고리즘
이전에 풀었던 LIS문제와 다르게
이 문제는 길이가 아니라 합을 기준으로 해야 한다.
1. DP 배열 정의
먼저, 수열을 seq[0] ~ seq[n-1] 라고 할 때,
💡 DP 리스트의 정의
dp[i]=seq[i]를 마지막 원소로 가지는 “증가 부분 수열”들 중, 합이 가장 큰 값
2. 초기값 설정
처음에는 각 원소 하나만 선택한 경우를 생각하면 되기 때문에,
dp[i] = seq[i]를 만족하도록 초기화할 수 있다.
파이썬에서는 아래처럼 한 줄로 처리:
dp = seq[:] # 원본과 독립된 새 리스트 (깊은 복사 느낌)나중에 반복문을 돌면서 “앞에 다른 수를 붙일 수 있는 경우들”을 고려해 dp[i]를 점점 키워 나간다.
3. 점화식 세우기
i번째 위치에 seq[i]가 있을 때,
그 앞에 올 수 있는 인덱스 j는 다음 조건을 만족해야 한다.
- 항상 앞에 있어야 하니까:
0 ≤ j < i - 증가 수열이어야 하니까:
seq[j] < seq[i]
이 조건을 만족하는 모든 j에 대해,
dp[i] = max(dp[i], dp[j] + seq[i])
라고 갱신해 주면 된다.
즉,
- “나보다 작은 값들 중에서”
- “그 값으로 끝나는 증가 부분 수열의 합(
dp[j])이 가장 큰 것”을 골라 - 거기에 나(
seq[i])를 붙여서 새로운 합을 만드는 과정이다.
시간 복잡도
- 이중 for문 (
i에 대해0 ~ n-1,j에 대해0 ~ i-1)
→ 최악의 경우 약n * (n-1) / 2번 연산 - 시간 복잡도: O(n²)
n의 범위가 크지 않기 때문에, 이 정도 복잡도로 충분히 통과 가능하다.
✅ 최종 코드
n = int(input())
seq = list(map(int, input().split()))
dp = seq[:]
for i in range(1, n):
for j in range(i):
if seq[i] > seq[j]:
dp[i] = max(dp[i], dp[j] + seq[i])
answer = max(dp)
print(answer)
📚 파이썬에서 얕은 복사 vs 깊은 복사 정리
또 하나의 시행착오는 리스트 복사 문제였다.
처음에 아래처럼 썼는데:
dp = seq이렇게 하면 동일한 리스트를 가리키는 얕은 복사라서
dp[i]를 변경하면 seq[i]도 바뀌어버린다.
그래서 계산 과정이 꼬일 위험이 있었다.
이 문제에서는 원본을 건드리면 안 되기 때문에
아래처럼 반드시 깊은 복사 형태가 필요하다:
dp = seq[:] # 안전한 방법!✔ 얕은 복사 (Shallow Copy)
같은 리스트 객체를 바라본다.
seq = [1,2,3]
dp = seq
dp[0] = 100
print(seq) # [100, 2, 3] ← 원본도 바뀜✔ 깊은 복사 (Deep Copy)
새로운 리스트를 만든다(원본 영향 없음).
🔸 방법 1: 슬라이싱
dp = seq[:]🔸 방법 2: list() 생성자
dp = list(seq)🔸 방법 3: copy 모듈
(2차원 리스트 같은 복잡한 구조에서 유용)
import copy
dp = copy.deepcopy(seq)이번 문제는 1차원 리스트이기 때문에
seq[:] 만으로 충분했다.
