글 읽기 - LIS 이분탐색 반례좀 제발 찾아주세요 ㅠㅠ

hjy5405 5년 전 1

LIS 1번문제에 있는 반례까지 다 긁어모아서 다 해봤는데도 맞게나오는데

넣자마자 틀리다고 나오네요 ㅠㅠ 어딘가 틀렸으니깐 틀린거긴한데 도저히 못찾겠어요!

혹시 어느부분이 잘못됬는지 알려주실수 있나요?? ㅠㅠ

반례라도 주시면 감사드립니다!

n = int(input())
a = list(map(int,input().split()))
dp = [a[0]]
for i in range(1,n):
    if a[i] > dp[-1]:
        dp.append(a[i])
    else:
        st = 0
        en = len(dp) - 1
        mi = (st+en)//2
        while True:
            if a[i] > dp[mi]:
                st = mi
            elif a[i] < dp[mi]:
                en = mi
            else:
                break
            if en - st <= 1:
                if dp[st] != a[i]:
                    dp[en] = a[i]
                break
            mi = (st+en) // 2
print(len(dp))

Rose 5년 전 1

https://ideone.com/gMubmj

8
10 20 30 5 10 20 30 40
정답: 5
질문자님의 답: 6

xcm1321 5년 전 13

반례 드립니다

10
4 7 10 3 1 8 7 2 5 7
Answer: 4 Output: 5
7
7 9 10 8 2 3 7
Answer: 3 Output: 4
10
7 10 8 10 1 2 9 9 1 10
Answer: 4 Output: 5
9
2 8 3 10 5 1 5 2 3
Answer: 3 Output: 4
10
10 6 5 9 10 9 3 4 7 1
Answer: 3 Output: 4
10
5 8 10 3 9 1 5 8 5 6
Answer: 3 Output: 4
9
3 2 8 2 10 1 2 2 3
Answer: 3 Output: 4
10
3 8 10 1 5 7 9 8 9 6
Answer: 5 Output: 6
7
4 3 4 9 1 3 7
Answer: 3 Output: 4
10
8 6 8 9 5 1 4 4 6 3
Answer: 3 Output: 4

hjy5405 5년 전 1

와 반례가 왜 나오는지까지 찾았습니다!

두분다 감사드려요! ㅠㅠ

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

문제

문제

출처

ICPC

LIS 이분탐색 반례좀 제발 찾아주세요 ㅠㅠ

hjy5405 5년 전 1

Rose 5년 전 1

xcm1321 5년 전 13

hjy5405 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말