• 카테고리

    질문 & 답변

  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

증가하는 수열 응용문제

21.09.13 17:15 작성 조회수 123

0

안녕하세요 강사님.

질문에 앞서 강좌문제가 아닌 문제를 질문하여 죄송합니다.

증가하는 수열 문제를 응용한 문제를 백준(#14002)에서 풀어보았는데 답이 틀렸다고 나와서 질문드립니다.

제가 코드를 짜보았을때 반례는 이상이 없어보였습니다. 혹시 반례나 코드가 틀린부분이 있다면 조언 부탁드리겠습니다.

문제는 대략적으로 강사님께서 풀어주신 문제가 단순히 길이만을 나타내는 문제라면, 이 문제는 길이뿐아니라 순열까지 나타내는 문제입니다.

도움 주시면 감사합니다.

문제링크 ( https://www.acmicpc.net/problem/14002 ) 

import sys
sys.stdin = open('input.txt','rt')
 
n = int(input())
arr = list(map(int,input().split()))
arr.insert(0,0)
dp = [[0]*(2) for _ in range(n+1)]
dp[0][1]=[]
dp[1][0] = 1
dp[1][1]=[arr[1]]
for i in range(2,n+1):
    max=0
    c=[arr[i]]
    for j in range(i-1,-1,-1):
        if arr[i]>arr[j] and dp[j][0]>max:
            max = dp[j][0]
            b=dp[j][1]
            c=b+[arr[i]]
        elif arr[i]==arr[j]:
            b=dp[j][1]
            c=b
    dp[i][0] = max+1
    dp[i][1] = c
res=0
for i in range(1,n+1):
    if dp[i][0] > res:
        res = dp[i][0]
 
for i in range(1,n+1):
    if dp[i][0] == res:
        print(dp[i][0])
        for j in range(len(dp[i][1])):
            print(dp[i][1][j],end=' ')
        print()
        break
 
#for x in dp:
    #print(x)
course-thumbnail

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

답변 1

답변을 작성해보세요.

0

김태원님의 프로필

김태원

지식공유자

2021.09.15

안녕하세요^^

백준에서 채점이 안나오는 것은 저도 잘 모르겠습니다. 본인 코드이니 스스로 시간이 많이 걸리더라도 스스로 찾는게 좋을 것 같습니다.

위에 코드가 조금 복잡해보이기는 합니다. 영상 설명 코드에서 수열까지 출력하는 코드를 조금 더 붙여보았습니다. 14002문제는 입력수열의 길이가 1도 들어오는 res=1 초기화했습니다.

import sys
sys.stdin = open("input.txt", 'r')
n=int(input())
arr=list(map(int, input().split()))
arr.insert(0,0)
dy=[0]*(n+1)
dy[1]=1
res=1
for i in range(2, n+1):
    max=0
    for j in range(i-1, 0, -1):
        if arr[j]<arr[i] and dy[j]>max:
            max=dy[j]
    dy[i]=max+1
    if dy[i]>res:
        res=dy[i]
print(res)
answer=[]
for i in range(n, 0, -1):
    if(dy[i]==res):
        answer.append(arr[i])
        res-=1
answer.reverse()
for x in answer:
    print(x, end=' ')

 

 

이 글과 비슷한 Q&A