글 읽기 - 논리가 타당한지 평가 부탁드립니다.

dusrlf13 3년 전 0

11053번의 코드와 출력부를 제외하고 완전히 동일합니다.

아마 입력 데이터가 최대 1000개이기 때문에 dp로 푸는 것이 가능하다고 하더라구요...(이 부분은 12015번을 풀며 알게됐습니다.)

제 생각에 dp배열이 오름차순으로 정리되고, 뒤의 LIS는 앞의 인덱스가 가지는 경우의 수를 포함하므로

단순히 가장 큰 dp배열의 값 부터 내림차순으로 모든 값들을 가질 수 있게 해주고(문제 테스트 케이스에서는 4가 최대이므로 4, 3, 2, 1을 모두 가질 수 있게)

이에 해당하는 입력값을 출력해줬습니다...

물론 각 2 혹은 3의 dp값을 가지는 입력값이 다 다르겠으나 이는 상관없다고 생각됩니다.

말을 정리하려고 노력했습니다만 잘 이해하실수 있게 썼을런지 모르겠네요 ㅠㅠ

제 생각이 맞는 논리인지 궁금합니다.

N = int(input())

array = list(map(int, input().split()))
dp = [1 for i in range(N)]
temp_list = list()
result = list()

for i in range(N):
    for j in range(i):
        if array[i] > array[j] and dp[j] + 1 > dp[i]:
            dp[i] = dp[j] + 1

temp = max(dp)

for i in range(len(dp)-1, -1, -1):
    if dp[i] == temp:
        result.append(array[i])
        temp -= 1
        if temp == -1:
            break

result.reverse()

print(max(dp))
for i in result:
    print(i, end=' ')

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

논리가 타당한지 평가 부탁드립니다.

dusrlf13 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말