글 읽기 - 반례를 도저히 못찾겠습니다. 도와주세요

hni1124 2년 전 1

질문 게시판 반례들 다 넣어도 정상동작하고 있어요..ㅠ

디피로 구현하였고 cnt배열의 [1]인덱스에다가 해당 인덱스[0]숫자의 뒤에 나오는 배열 중 자기자신보다 큰 것 && 부분 배열의 길이가 가장 큰것의 수를 입력해서

나중에 하나하나 역추적 해서 프린트 하는 방식입니다.

#2차원 dp를 활용
#-11053의 응용

#같은 숫자일때 누락은 없어보임 >>> 그 전에 이미 더 큰 값을 가진경우에 다른 숫자들에서 체크를 하기 때문에

import sys
n=int(input())
L=list(map(int,(sys.stdin.readline().strip().split())))
# 500 1 501 502 2 3 1000 10 50
# 500 50 501 502 2 3 1000 10 1
cnt=[[0,0] for _ in range(1001)]
# 아니면 그냥 스택으로 처리하는게 나아보일수 있음
def dp(m):
	max=0
	forward = 0
	for i in range(m,n):
		if L[m]<L[i]:
			if max<=cnt[L[i]][0]:
				max = cnt[L[i]][0]
				forward=L[i]
	cnt[L[m]][0]=max+1
	cnt[L[m]][1]=forward

j=n-1
while(j>=0):
	#dp에는 값이 아닌 인덱스를 넘길것
	dp(j)
	j-=1


maxx=0
index=0

#제일 큰 값을 가지는 배열의 시작지점과 그것의 인덱스를 저장하돼, 맨 뒤에 나오는 인덱스에 대해서 저장하고 있는다.
for i in range(1001):
	if maxx <= cnt[i][0]:
		maxx = cnt[i][0]
		index=i

print(maxx)

for k in range(maxx):
	if k==(maxx-1):
		print(index)
	else:
		print(index,end=' ')
	index=cnt[index][1]

bamgoesn 2년 전 2

반례입니다

7
3 1 5 2 3 6 4

출력
4
1 2 3 5

길이 4는 정답이지만 1 2 3 5는 입력된 수열의 부분수열이 아님

hni1124 2년 전 0

와... 감사합니다. ㅠㅜ 이런거 찾는거도 실력인데 참 어렵군여

ssac_sim 11달 전 0

3 1 5 2 3 6 4를 했을때,

길이가 왜 4가 되나요?

3 5 6 했을때가 best 아닌가요??

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

문제

문제

출처

ICPC

반례를 도저히 못찾겠습니다. 도와주세요

hni1124 2년 전 1

bamgoesn 2년 전 2

hni1124 2년 전 0

ssac_sim 11달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말