11055. 가장 큰 증가 부분 수열

문제 링크

11055. 가장 큰 증가 부분 수열

문제 코드

N = int(input())

num_list = list(map(int,input().split()))

now = [0]*N

maxist = -1

for i in range(N):
    if i ==0:
        now[i] = num_list[i]
        maxist = now[i]
        continue

    for j in range(i - 1, -1, -1):
        if num_list[i] > num_list[j]:
            tmp = num_list[i] + now[j]

            if tmp > now[i]:
                now[i] = tmp
        if now[i] == 0:
            now[i] = num_list[i]

    for i in range(N):
        if now[i] > maxist :
            maxist = now[i]

print(maxist)

문제 풀이

• 본인보다 작은 값들을 찾아 가면서 tmp에 더해서 저장한다.
• 다 찾아보면서 가장 큰 값을 now에 저장한다.
• 최종적으로 now의 maximum 값을 저장한다.

1등 코드 해석

arr = [0]*1001
for i in range(N):
	arr[num_list[i]] = max(arr[num_list[:i]])+num_list[i] 
print(max(arr)))

• 1001개의 배열을 미리 생성
• arr의 index는 num_list의 값
• arr의 값을 갱신할때는 이전 값들중 가장 max인 값을 가져와서 더해서 저장해줌
  - 없으면 본인 값 들어감
  • 이럴경우 연산의 개수가 훨씬 줄어듬