[BOJ] 11722 가장 긴 감소하는 부분 순열 Python (복습)

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

11722번: 가장 긴 감소하는 부분 수열

가장 긴 감소하는 부분 수열

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

28216

17740

14495

63.869%

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

풀이 코드 (정답 참고)

처음 풀 때 도저히 점화식을 생각해낼 수 없어서 막무가내로 구현했다.. (틀림)

import sys
input = sys.stdin.readline

n = int(input())
graph = list(map(int, input().split()))

ans = []
tmp = []
for i in range(1, n):
    print(ans, graph[i-1], graph[i])
    if graph[i-1] == graph[i]:
        print(graph[i-1], graph[i])
        continue
    # 감소하는 경우
    if graph[i-1]>graph[i]:
        if len(ans) >= 1 and ans[-1] == graph[i-1]:
                ans.append(graph[i])
        if len(ans) == 0:
            ans.append(graph[i - 1])
            ans.append(graph[i])
        else:
            ans.append(graph[i])
    # 증가하는 경우
    else:
        if len(ans) >= 1 and ans[0] < graph[i]:
            continue
        tmp.append(len(ans))
        for j in range(len(ans)-1, -1, -1):
            if ans[j] > graph[i]:
                ans.append(graph[i])
            else:
                ans.pop(j)

    tmp.append(len(ans))
    print(ans)
print(max(tmp))

dp문제는 이렇게 푸는게 아니라 무조건 규칙을 찾아야 한다.

참고한 코드

import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int, input().split()))
dp = [1 for i in range(n)]
for i in range(n):
    for j in range(i):
        if nums[j] > nums[i]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))

이 풀이는 이중 for문을 이용한 풀이로, 현재 인덱스와 그 앞의 모든 수를 비교한다.

시간복잡도 O(N^2)

 

코드의 원리는 이러하다.

- 앞의 수가 다음 수보다 크다면 문제의 조건 만족

- 각 인덱스에 대해 자신보다 인덱스가 작은 값 검색하여 (두 번째 for문) 조건을 만족하는 수의 개수를 찾는다.

- 앞의 인덱스에서 조건을 만족하는 수의 개수 찾으면, 다음 계산시에 이를 이용한다.

 

즉,

 

nums[j] > nums[i] 일 때 문제의 조건 만족

조건을 만족하는 수의 개수를 dp[i]에 저장해야 한다.

 - 만약 nums[i]가 문제의 조건 만족한다면, 이전의 최대값인 dp[j]에 1을 더한 값이 dp[i]가 될 것이다.

- nums[i]가 조건을 만족하지 못한다면, dp[i]는 이전의 값 그대로인 dp[i]