[백준] 11053번 : 가장 긴 증가하는 부분 수열 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

11053번: 가장 긴 증가하는 부분 수열

 

1. 문제 설명

2. 풀이과정

해당 문제는 각 수까지 부분 수열에서 최대로 긴 증가하는 부분 수열의 길이를 구하면 된다.

처음 최소 길이 1로 초기화한 배열을 가지고 수열에서 각 수를 가져와 수열의 이전 값들과 비교한다.

만약 가져온 수가 더 크다면 비교한 값의 부분 수열 길이에 1을 더한 결과와 현재 수의 부분 수열 길이를 비교하여 더 큰 결과를 가져온 수의 부분 수열 길이로 저장한다.

이 과정은 가져온 수까지의 수열에서 해당 값이 가능한 긴 증가하는 부분 수열의 길이를 구하는 과정이다.

수열의 마지막 수까지 반복한 뒤, 부분 수열의 길이 값 중 최대의 값을 출력하면 된다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 수열의 크기를 입력받는다. N = int(sys.stdin.readline())
3. 수열의 값을 입력받아 리스트로 저장한다. A = list(map(int, sys.stdin.readline().split()))
4. 가능한 부분 수열의 길이를 저장할 리스트를 생성하고 최소 부분 수열의 길이인 1로 초기화한다. dp = [1] * N
5. 첫 번째 수열의 값은 최대 부분 수열의 길이가 1이므로 두 번째 수열의 값부터 계산한다. for i in range(1, N)
6. 수열에서 해당 값의 이전 값들을 하나씩 추출하여 for j in range(i)
7. 해당 값과 비교하고 만약 해당 값이 더 크다면 if (A[j] < A[i])
8. 해당 값까지 가능한 최대 부분 수열 길이의 값을 비교한 값의 가능한 최대 부분 수열의 길이에 1을 더한 값과 해당 값의 가능한 최대 부분 수열 길이의 값 중 더 큰 값을 저장한다. dp[i] = max(dp[j] + 1, dp[i])
9. 수열의 마지막 수까지 가능한 최대 부분 수열의 길이를 구했으면 부분 수열의 길이를 저장한 리스트에서 최댓값을 출력한다. print(max(dp))

반응형

3. 소스코드

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

dp = [1] * N
for i in range(1, N):
    for j in range(i):
        if (A[j] < A[i]):
            dp[i] = max(dp[j] + 1, dp[i])

print(max(dp))