(BOJ)-11053, Python

문제 요약

출처: (BOJ)11053 - 가장 긴 증가하는 부분 수열

길이가 $N$개인 수열이 주어지고, 이 수열의 부분 수열 중 길이가 가장 긴 증가하는 수열을 구하는 문제이다.

접근 과정

1. 완전탐색 접근(For문)

이 문제를 보자마자 느낀 것은 경우의 수를 쪼갤 수 없다는 것이었다. 그래서 재귀가 아닌 for문을 사용하여 완전 탐색을 해보자는 생각으로 접근했다. 시간 초과가 발생할 것이라고 예상했지만, 결과는 틀렸습니다라는 답이 나왔다. 내가 틀린 이유를 모르겠다..

내가 생각한 접근 방법은 다음과 같다:

• 예를 들어, 수열 [1, 10, 2, 4]이 주어졌다고 가정해보자.
  1. 4를 기준으로, 1, 10, 2와 비교를 수행한다.
  2. 먼저, 4 > 1이므로 길이가 1 증가하여 2가 된다. 이후, 다음에 올 원소는 1보다 크고 4보다 작아야 한다.
  3. 다음으로, 4 < 10이므로 조건을 충족하지 않아 continue 한다. 여전히 다음에 올 원소는 1보다 크고 4보다 작아햐 한다.
  4. 마지막으로, 4 > 2이므로 길이가 1 증가하여 3이 된다.

시도한 코드

N = int(input())
arr = list(map(int, input().split()))
m_len = 1 

for i in range(1, N): 
    _len = 1 
    m_v = 0
    for j in range(i):  
        if arr[i] > arr[j] and m_v < arr[j]: 
            m_v = arr[j]
            _len += 1
                
    m_len = max(m_len, _len)

print(m_len)

2. DP 접근(점화식)

위에서 해결하지 못해 찝찝했지만, 이전 접근 방법에서 생각한 논리를 바탕으로 점화식 기반 DP로 넘어가 보았다. 결과는 맞았습니다!

코드 구현

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

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

print(max(dp))

회고

두 접근 방식은 모두 같은 논리라고 생각하지만, 분명히 틀린 이유가 있을 것이다. 그 이유가 뭔지 너무 궁금하다. 조금 더 고민해보고, 추후에 해결이 되면 업데이트해야겠다.