글 읽기 - 마지막부분에서 틀렸습니다. 나오는데 왜그런건가요 ?ㅠㅠ(파이썬)

hyukk97 3년 전 0

제 알고리즘은 전투력은 내림차순이면서 병사번호를 기준으로 가장 긴 수열을 만드는 것입니다.

그래서 일단 처음에 전투력을 리스트로 입력받으면 "병사번호 = 인덱스번호" 이므로 (인덱스번호, 전투력)를 요소로하는 새로운 리스트를 만듭니다.

그래서 전투력을 기준으로 내림차순을 정렬한 뒤 인덱스번호를 기준으로 가장 긴 수열을 만드는 것입니다.

그런데.. 마지막에서 계속 틀렸습니다.라고 나옵니다. ㅠㅠ 알려주세요 선배님들!!

n = int(input())
n_list = list(map(int,input().split())) # 병사 리스트 입력
new_list = [] # (병사번호, 전투력) 형태로 입력 될 리스트
dp = [1] * n # 수열길이 최소값 1로 dp테이블 초기화

# 전투력은 내림차순이고 병사번호는 오름차순이어야 하므로 set으로 이루어진 리스트 생성
for i in range(n):
    new_list.append((i,n_list[i]))

# 전투력을 기준으로 내림차순 정렬
new_list = sorted(new_list, key=lambda x:x[1], reverse=True)

# 전투력은 이미 내림차순상태이므로 인덱스번호를 기준으로 가장 긴 수열 만들기!!
for i in range(1, n):
    for j in range(0,i):
        if new_list[i][0] > new_list[j][0]:
            dp[i] = max(dp[i], dp[j]+1)

print(n - max(dp))

ryuch91 2년 전 1

4 4 4 4

위 테스트 케이스처럼 다 같은 경우에는 실패합니다.

인덱스번호로 비교하다보니 power가 같을 때도 수열의 길이가 늘어나는 것 같네요

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

문제

문제

출처

ICPC

마지막부분에서 틀렸습니다. 나오는데 왜그런건가요 ?ㅠㅠ(파이썬)

hyukk97 3년 전 0

ryuch91 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말