[파이썬/Python] 백준 11722번: 가장 긴 감소하는 부분 수열

숨·2024년 8월 18일

코테

알고리즘 문제 풀이

목록 보기

54/105

📌 문제 : 백준 11722번

📌 문제 탐색하기

N : 수열의 크기 $(1 ≤ N ≤ 1,000)$
A : 주어진 수열 $(1 ≤ A_{i} ≤ 1,000)$

수열 전체에서 감소하는 숫자들을 찾아 만든 부분 수열 중 가장 긴 수열의 길이를 찾아 출력하는 문제이다.

문제 풀이

⭐️ 감소하는 숫자 찾는 법

해당 수열로 만들 수 있는 부분 수열 중 감소하는 숫자들로 구성한 경우를 찾는다.

이전의 값들 중 현재 값보다 큰 경우가 있는지 확인하고 그 수를 센다.

최대 길이의 부분 수열 내에 있는 숫자들은 이전 숫자까지의 부분 수열 개수에 1을 더한 값을 수열의 길이로 갖는다.

위의 방법을 정리해보면 다음과 같다.
1️⃣ 각 요소를 접근하면서 현재 수가 이전보다 작은지 확인한다.
2️⃣ 현재보다 더 작은 요소가 몇 개인지 누적해서 센다.

개수를 누적해서 셀 수 있기 때문에 부분 수열의 길이를 dp 테이블 값에 채워주면서 마지막으로 최댓값을 출력하도록 구현한다.

이전 값까지의 최대 길이에 1을 증가시킨 값(﹦ 현재 값을 부분 수열에 넣었을 때의 수열 길이)을 dp 테이블에 넣어주면서 최댓값을 구해야 한다.
max() 함수를 이용해 조건에 맞을 때 개수를 늘려주면서 현재 값보다 큰 값을 테이블에 채울 수 있도록 한다.

가능한 시간복잡도

DP 테이블 채우기 → $O(N^2)$

최종 시간복잡도
총 $O(N^2)$ 이 된다.
최악의 경우 $O(10^6)$ 이므로 이는 1초 내에 연산이 가능하다.

알고리즘 선택

DP로 최대 길이 구하기

DP 구현

1️⃣ dp 테이블를 정의한다.
2️⃣ dp 테이블의 초기값 계산한다.
3️⃣ 조건에 따라 dp 테이블을 채워준다.
4️⃣ dp 테이블의 마지막 값을 출력한다.

📌 코드 설계하기

N 입력
A 입력
dp 테이블 만들기
dp 테이블 채우기
결과 출력

📌 시도 회차 수정 사항

1회차

# DP 테이블 초기화
dp = [0] * N

dp 테이블을 초기화 할 때 0으로 값을 채웠는데 예제1의 출력이 1이 작은 값이 나왔다.
부분 수열을 요소 하나만으로도 만들 수 있기 때문에 수열 길이를 의미하는 dp값을 1로 초기화해주어야 했던 것이다.

2회차

# dp 테이블 채우기
for i in range(1, N):
    for j in range(i):
        if A[j] > A[i]:
            dp[i] = dp[j] + 1

dp 테이블을 채울 때 더 작은 값이 있을 때 길이를 바로 증가시켜주는 방식으로 넣었더니 예제는 잘 작동했지만 틀렸습니다가 나왔다.
바로 덮어쓰게 되기 때문에 최댓값이 보장되지 않기 때문이다.

📌 정답 코드

import sys

input = sys.stdin.readline

# N 입력
N = int(input())

# A 입력
A = list(map(int, input().split()))

# dp 테이블 초기화
dp = [0] * N

# dp 테이블 채우기
for i in range(1, N):
    for j in range(i):
        if A[j] > A[i]:
            dp[i] = max(dp[i], dp[j] + 1)

# 결과 출력
print(max(dp))