94. 백준 11053 번 파이썬 코드 및 자세한 설명

안녕하세요 코딩하는 덕구입니다.

다이나믹 프로그래밍 문제인 BOJ 11053 번 가장 긴 증가하는 부분 수열 입니다.

https://www.acmicpc.net/problem/11053

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

 

먼저 백준 11053 번 파이썬 정답 코드입니다. 설명은 아래에 있습니다.

N = int(input())
A = list(map(int, input().split()))
dp = [1 for _ in range(N)]

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

print(max(dp))

 

문제 요약

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고,

길이는 4 입니다.

부분 수열 중 가장 긴 증가하는 부분 수열의 길이를 찾아 출력하는 문제입니다.

 

문제 접근

예제의 가장 긴 부분 수열을 구하는 방법입니다.

예를들어 수열 A에서 6번째 까지의 가장 긴 부분 수열은

5번째 숫자 까지 가장 긴 부분 수열 + 1이 됩니다.

즉 i 번째 까지의  가장 긴 부분 수열 = i - 1 까지 가장 긴 부분 수열 + 1

 

파이썬 코드 구현

먼저 수열 A 를 입력받고, i 번째 수 까지의 가장 긴 부분 수열을 저장할 리스트 dp 를 구현합니다. 

최소 자기 자신이 수열이 되므로 모두 1로 초기화 했습니다.

N = int(input())
A = list(map(int, input().split()))
dp = [1 for _ in range(N)]

 

이중 for문을 이용하여 i 번 째 부분수열은 i 보다 작은 숫자 중 가장 긴 부분수열 + 1

이 되도록 코드를 작성했습니다.

if dp[i] <= dp[j] (만약 j 번째 부분 수열이 i 번째 까지의 부분수열 - 1 보다 크다면)

i 번째 까지의 가장 긴 부분수열 = j 번째 까지의 가장 긴 부분수열 + 1 (i > j)

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

이제 부분수열 중 가장 긴 길이의 부분수열을 출력하면 됩니다.

print(max(dp))

 

백준 11053 번 가장 긴 증가하는 부분 수열 파이썬 최종 코드입니다.

N = int(input())
A = list(map(int, input().split()))
dp = [1 for _ in range(N)]

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

print(max(dp))

 

백준 11053 번 가장 긴 증가하는 부분 수열 자세한 설명 및 파이썬 코드였습니다.

감사합니다.