1. 오늘의 문제
오늘 문제는 어제 나왔던 최장 증가 부분 수열의 응용버전이다.
어제 나왔던 문제와 비슷함.
27일차 TIL은 도저히 쓸 시간이 나지 않아서 오늘거로 때우려고 한다.
역시 매일 과제가 있는 프로젝트는 주말이 위기다.
문제
수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
2. 원리
최장 증가 부분 수열이 쉽게 이해되지 않아서 주말동안 어떻게 쉽게 이해할 수 있을지를 한참 고민한 것 같다.
문득 아침에 그런 생각이 들었다.
'그냥 앞쪽 값이 현재값보다 작으면 단순하게 꼬리를 붙이는 방식이다.'
그래서 반복문으로 꼬리에 꼬리를 물면 모든 수열의 최대 길이가 나온다.
그런데 이번 백준문제의 문제점은 합을 더하다 보면, 이전보다 더 작은 값이 나올수 있다는 것.
아래의 테스트 케이스를 보자.
10
2 11 3 14 1 200 100 5 101 13
단순히 수열을 더해주기만 하면 각 구간에서의 합이 [2, 13, 5, 19, 1, 201, 101, 6, 107, 19] 으로 나온다.
왜냐하면 14에서 200으로 넘어가는 구간에서 200은 14보다도 크고, 1보다도 크기 때문에 값이 덮어져 버린다.
그래서 if문 내부에서 합산한 값을 비교하는 구문을 조금 추가했다.
3. 코드
from sys import stdin
put = stdin.readline
num = int(put())
numsLst = list(map(int, put().split()))
totals = [0 for k in range(num)]
for i in range(num):
thisNum = numsLst[i]
totals[i] = thisNum
for j in range(0, i):
if numsLst[j] < numsLst[i] and totals[i] < totals[j] + thisNum :
totals[i] = totals[j] + thisNum
print(max(totals))
4. 느낀점
최장 증가 부분 수열을 이전에 한번 본 적이 있었는데 이번에 완전하게 이해한 것 같다.
이게 중간정도의 난이도를 가진 알고리즘이라고 하니, 아직 가야할 길이 멀게 느껴졌다.
다음 스터디에서는 첼린저에 한번 도전해 보고싶다.
