[백준 11055 파이썬/python] 가장 큰 증가하는 부분 수열

가장 큰 증가하는 부분 수열

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	43844	19759	15700	44.699%

문제

수열 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)

출력

첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.

예제 입력 1

10
1 100 2 50 60 3 5 6 7 8

예제 출력 1

113

풀이

n = int(input())
a = list(map(int,input().split()))
d = [0]*n
for i in range(n):
    d[i] = a[i]
    for j in range(i):
        if a[j] < a[i] and d[j]+a[i] > d[i]:
            d[i] = d[j]+a[i]
print(max(d))

1. n = int(input()): 사용자로부터 입력 받은 숫자를 정수형으로 변환하여 변수 n에 저장합니다.

2. a = list(map(int,input().split())): 사용자로부터 입력 받은 숫자들을 공백을 기준으로 나눈 후 정수형으로 변환하여 리스트 a에 저장합니다.

3. d = [0]*n: 길이가 n인 0으로 초기화된 리스트 d를 생성합니다. d는 각 위치에서 최대 부분 수열의 합을 저장하는 목적으로 사용됩니다.

4. for i in range(n):: 인덱스 i를 0부터 n-1까지 반복합니다.

5. d[i] = a[i]: d[i]의 초기값을 a[i]로 설정합니다.

6. for j in range(i):: 인덱스 j를 0부터 i-1까지 반복합니다.

7. if a[j] < a[i] and d[j]+a[i] > d[i]:: a[j]가 a[i]보다 작고, d[j]에 a[i]를 더한 값이 d[i]보다 클 경우 조건문을 실행합니다.

8. d[i] = d[j]+a[i]: 조건문이 참일 때, d[i]의 값을 d[j]+a[i]로 업데이트합니다.

9. print(max(d)): d 리스트에서 가장 큰 값을 출력합니다. 이 값이 주어진 수열에서 가장 긴 증가하는 부분 수열의 합입니다.

Uploaded by N2T