글 읽기 - 반례 찾아서 해봤고 너무 힘들어서 도움 구합니다.

seok9211 3년 전 0

구글링 참고해서 경로를 찾아내는 방법을 이것저것 다 해봐도 pass가 되질 않습니다.

게시판 반례는 다 찾아서 해본 것 같습니다.

사용한 알고리즘은 이분 탐색 입니다.

혹시 LIS 알고리즘에 따라 경로를 추적하는 방법이 다른지도 궁금하고,

어떤 부분을 수정해야하는지, 이 코드를 벗어나는 반례는 또 어떤 것이 있는지 조언 부탁드립니다 ;

import sys
from bisect import bisect_left

r = sys.stdin.readline

length = int(r())
board = list(map(int, r().split()))
# parent = {}
parent = [-1] * length
result = []
for i in range(length):
    # print(result)
    # print(parent)
    if len(result) == 0:
        # parent[board[i]] = -1
        parent[i] = 0
        result.append(board[i])
    else:
        if board[i] > result[-1]:
            # parent[board[i]] = result[-1]
            parent[i] = len(result)
            result.append(board[i])
        elif result[-1] > board[i]:
            temp = bisect_left(result, board[i])
            result[temp] = board[i]
            parent[i]=temp
        else:
            continue
print(len(result))
# print(result)
# print(board)
# print(parent)
result2 = []
# target = result[-1]
# while target != -1:
#     result2.append(target)
#     target = parent[target]
t = len(result) - 1
for i in range(length - 1, -1, -1):
    if parent[i] == t:
        result2.append(board[i])
        t -= 1
for item in result2[::-1]:
    print(item, end=" ")

shg9411 3년 전 4

3 3 1

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

문제

문제

출처

ICPC

반례 찾아서 해봤고 너무 힘들어서 도움 구합니다.

seok9211 3년 전 0

shg9411 3년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말