백준 11053 가장 긴 증가하는 부분수열 파이썬

백준 11053 가장 긴 증가하는 부분 수열 풀이

접근방식

1. 가장 긴 증가하는 부분 수열이 반드시 주어진 수열의 첫번째부터 시작하는 것이 아니라는 점 인지하기
2. 각각의 원소마다 증가하는 부분 수열이 시작이 될 수 있다는 점 인지하기
3. 따라서, 각 원소를 시작점으로 하여 모두 1을 가지는 dp 리스트 생성하기
4. 자기 자신보다 이전의 수들을 비교하면서 증가한다면 1씩 더해주기
5. max함수를 이용하여 가장 큰 값 출력하기

import sys

input = lambda: sys.stdin.readline().rstrip()

n = int(input())

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

dp = [1] * n

for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

4번의 오답 끝에 답을 도출할 수 있었습니다.

가장 처음 한 실수는 첫번째 원소를 기준으로 가장 긴 부분 수열을 구하려 한 것이고,

두 번째는 2중 for문을 통해 원소를 비교할 때, 처음부터 자기 자신 이전이 아니라,

자기자신과 바로 이전 원소만을 비교하여 길이를 구하지 못한 점입니다.

이 문제에서 까다로웠던 부분은 부분 수열의 시작점이 모든 원소가 가질 수 있다는 점과

2중 for문에서 아래 부분을 어떻게 도출할 것인가라고 생각합니다.

    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j] + 1)

해당 문제는 실버 2레벨 수준의 다이나믹 프로그래밍 문제이고,

연습에 도움이 되는 좋은 문제라고 생각합니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.
Just do it & Keep steady