글 읽기 - 반례부탁드립니다ㅠㅠ

fkeldn22 1년 전 0

질문에 있는 다양한 반례들 넣어봐도 정답이 나옵니다,,,

import sys

n=int(sys.stdin.readline())
p=list(map(int,sys.stdin.readline().split()))

dp=[0]*n
dp[0]=1

for i in range(1,n):
    l=[]
    for j in range(i):
        if p[j]<p[i]:
            l.append(p.index(p[j]))
    if l:
        dp[i]=max(dp[k] for k in l)+1
    else:
        dp[i]=1
print(max(dp))

jonghp1128 1년 전 2

answer로 적어드린 수열 외에도 다른 LIS 수열이 존재할 수 있습니다. 그래도 그 길이는 7로 같습니다.

제가 봤을 땐 13번 줄에 p.index 부분이 문제를 일으키는 것 같습니다.

index 함수가 리스트의 가장 앞부터 순차탐색을 하면서 target을 만나면 탐색을 멈추고 target의 인덱스를 가져오는 걸로 알고 있습니다.

그래서 같은 수가 수열에 두 개 이상 존재하면 문제를 일으키는 것이죠.

물론 제 의견이 틀린 의견일지도 모릅니다. 아래 반례에서 답을 찾으셨으면 좋겠습니다.

20
31 84 18 62 35 77 23 53 60 94 3 77 60 51 42 18 83 85 63 51
    
# answer
# 18 23 53 60 77 83 85
7
    
# yours
6

fkeldn22 1년 전 0

감사합니다 index함수를 쓰는게 문제였네요! 좀 더 수정해서 풀었습니다. 댓 감사합니다

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

문제

문제

출처

ICPC

반례부탁드립니다ㅠㅠ

fkeldn22 1년 전 0

jonghp1128 1년 전 2

fkeldn22 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말