글 읽기 - 반례질문

jintak0401 3년 전 0

반례가 뭘까요?

N 개의 수를 N - 1번의 for 문을 돌면서 LIS 를 구하는 방식으로 풀었습니다.

from sys import stdin
from bisect import bisect_left

input = stdin.readline

def solve():
    
    N = int(input())
    arr = list(map(int, input().split()))

    if N == 1:
        print(1)
        return

    ans = 0

    for i in range(N - 1):
        dp = [arr[0]]
        for j in range(1, i + 1):
            if dp[-1] < arr[j]:
                dp.append(arr[j])
            else:
                dp[bisect_left(dp, arr[j])] = arr[j]
        tmp = len(dp)
        dp = [arr[N - 1]]
        for j in range(N - 2, i, -1):
            if dp[-1] < arr[j]:
                dp.append(arr[j])
            else:
                dp[bisect_left(dp, arr[j])] = arr[j]
        tmp += len(dp)

        if arr[i] == arr[i + 1]:
            tmp -= 1
        
        if tmp > ans:
            ans = tmp
            
    print(ans)
    return

solve()

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

문제

문제

출처

ICPC

반례질문

jintak0401 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말