DP 11053관련 질문있습니다.

Question

안녕하세요, DP 백준 11053문제관련해서 질문이 있습니다. 1) 부분수열중 가장 긴 거라했으니 N = int(input()) lit = list(map(int, input().split())) print(len(sorted(list(set(lit))))) 이렇게 set으로 중복처리를해주고 그 길이를 구하면 안되는건가요? 2) 1) 방법이 틀려 부분수열이 아니라 기존에 input값에서 길이를 구하는걸로 구했을때 하기와 같이 했습니다. N = int(input()) lit = list(map(int, input().split())) dp = [0] * (N+1) for i in range(1, N): dp[i-1] = (lit[i] - lit[i-1]) print(sum([1 for i in dp if i>0])+1) 이전값과 비교하여 양수이면 남기고 남겨진값들로 길이를 구하려했는데 1), 2) 방법에서 둘 다 채점이 틀려서 제가 문제 자체를 이해를 잘못하고 있는지 하여 문의드립니다.

ally · Answer

안녕하세요, tocc22님! 부분수열의 정의에 대해 혼동을 하여 발생한 문제 같습니다. 부분수열 은 기존 수열에서 원래 순서를 유지한 채 일부 원소를 골라내어 만든 새로운 수열을 의미합니다. 따라서, 입력으로 주어진 수열에 대해 순서를 바꾸면 안됩니다!   질문해주신 코드에 대해 반례 테스트 케이스를 첨부하였으니 참고하시면 좋을 거 같습니다!   [1번째 코드의 반례 테스트 케이스] 7 10 20 10 30 20 50 40 답은 4이며, 길이가 4인 부분 수열의 후보는 {10, 20, 30, 40} 또는 {10, 20, 30, 50} 이 있습니다.   [2번째 코드의 반례 테스트 케이스] 8 1 2 1 2 1 2 1 2 답은 2이며, 길이가 2인 부분 수열의 후보는 {1, 2} 가 있습니다.   질문에 대해 만족스러운 답변이 되었기를 바랍니다! 추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄