글 읽기 - 시작하자마자 "틀렸습니다."입니다.

qkreltms 5년 전 0

제가 작성한 코드는 no. 1입니다.(정답은 no. 2)

11054 문제는

증가하는 수열의 최대 길이와 감소하는 수열의 최대 길이를 구하고, 그 후 각 자리의 최대 길이를 서로 더해준 후 max 값을 구하는 문제입니다.

eg: 1 2 3 2 1 일 때 => 5

제가 구현한 코드의 원리는 먼저 0 부터 n까지 증가하는 수열의 최대 길이를 구한 후 1 2 3 2 1 일 때 => 3,

최대값이 나온 인덱스 즉 2번째 부터 n까지 다시 감소하는 수열의 최대 길이를 구했습니다. 1 2 3 2 1 => 3

그 후 서로의 값을 더한 뒤 => 6 에서 3이 겹침으로 -1을 해서 결과는 5 입니다.

=> 1

1 5 2 1 4 3 4 5 2 1

=> 7

5
10 20 30 25 20

=> 5

10 20 30 40 20 30

=> 5

문제에서 주어진 테스트 케이스에서는 예상했던 값이 잘 나오는데 어느 경우에 틀리는지 감을 못 잡겠습니다...

#https://www.acmicpc.net/problem/11053
n = int(input())
A = list(map(int, input().split()))
d = [0] * n
d2 = [0] * n
for i in range(n):
    d[i] = 1
    for j in range(i):
        if A[i] > A[j]:
            d[i] = max(d[i], d[j]+1)
# no. 1
# D = max(d)
# b = d.index(D)
# for i in range(b, n):
#     d2[i] = 1
#     for j in range(i):
#         if A[i] < A[j]:
#             d2[i] = max(d2[i], d2[j]+1)
#
# D2 = max(d2)
# ans2 = D + D2 - 1
# print(ans2)

​# no. 2
d2 = [0] * n
for i in range(n-1, -1, -1):
    d2[i] = 1
    for j in range(n-1, i, -1):
        if A[i] > A[j]:
            d2[i] = max(d2[i], d2[j]+1)

ans = d[0]+d2[0]-1
for i in range(n):
    if ans < d[i]+d2[i]-1:
        ans = d[i]+d2[i]-1
print(ans)

jh05013 5년 전 1

풀이 과정을 설명해 주신 것은 좋습니다. 하지만 더 해야 되는 것이 있습니다.

질문을 올릴 때 "아래 공지사항을 먼저 읽고 글을 작성해 주세요." 라는 말이 나오는데 읽으셨나요? 그 글에 굵은 글씨로 "질문 검색을 먼저 해서 자신에게 필요한 답변이나 반례가 없는지 확인하고 질문을 남겨주세요." 라고 적혀 있습니다.

qkreltms 5년 전 0

@jh05013 젠틀하게 답변해주시네요. 참고하겠습니다.

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

문제

문제

출처

ICPC

시작하자마자 "틀렸습니다."입니다.

qkreltms 5년 전 0

jh05013 5년 전 1

qkreltms 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말