N = int(input())
arr = list(map(int, input().split()))
dp = [[1, 1] for i in range(N)]
result = []
for i in range(N):
for j in range(i):
if arr[j] < arr[i]:
dp[i][0] = max(dp[i][0], dp[j][0] + 1)
dp[i][0] = max(dp[i][0], dp[i-1][0])
for i in range(N-1, 0, -1):
for j in range(i-1, 0, -1):
if arr[j] > arr[i]:
dp[i][1] = max(dp[i][1], dp[j][1] + 1)
dp[i][1] = max(dp[i][1], dp[i-1][1])
for i in dp:
result.append(sum(i))
print(max(result))
주어진 예제 입력과 출력은 동일하게 나왔지만 이전 문제와 마찬가지로 오답처리되었습니다.
N = int(input())
arr = list(map(int, input().split()))
dp = [[1, 1] for i in range(N)]
result = []
for i in range(1, N): # 증가하는 수열의 최대길이 구하기
for j in range(i):
if arr[j] < arr[i]:
dp[i][0] = max(dp[i][0], dp[j][0] + 1)
dp[i][0] = max(dp[i][0], dp[i-1][0])
for i in range(N-1, -1, -1): # 감소하는 수열의 최대길이 구하기
for j in range(N-1, i, -1):
if arr[j] < arr[i]:
dp[i][1] = max(dp[i][1], dp[j][1] + 1)
for i in dp: # 바이토닉수열의 길이 할당
result.append(sum(i))
print(max(result) - 1) # 바이토닉수열의 최대길이 출력
정답 코드의 dp값(상)과 틀린코드의 dp값(하)
dp는 수열길이의 최대값을 저장하기때문에 dp의 인덱스가 커질수록 그 값은 크거나 같아진다고 생각했습니다.
따라서 코드 한 줄을 추가하여 그 기능을 수행하도록 했지만 틀렸다고 나옵니다.
왜 그런걸까.
감소수열은 수정하지 않아 모르겠지만 증가수열은 왜 틀린답인지 아직 원인을 찾지 못했습니다.
이해가 안되는 듯 헿
N = int(input())
arr = list(map(int, input().split()))
dp = [[1, 1] for i in range(N)]
result = []
for i in range(N): # 증가하는 수열의 최대길이 구하기
for j in range(i):
if arr[j] < arr[i]:
dp[i][0] = max(dp[i][0], dp[j][0] + 1)
for i in range(N-1, -1, -1): # 감소하는 수열의 최대길이 구하기
for j in range(N-1, i, -1):
if arr[j] < arr[i]:
dp[i][1] = max(dp[i][1], dp[j][1] + 1)
for i in dp: # 바이토닉수열의 길이 할당
result.append(sum(i))
print(max(result)) # 바이토닉수열의 최대길이 출력
우선 dp[i]에 [1,1]의 리스트를 할당합니다.
0인덱스는 증가하는 수열의 최대값, 1인덱스에는 감소하는 수열의 최대값이 할당될 예정입니다.
result 리스트에는 dp[i][0] + dp[i][1]의 값이 기록되어 바이토닉수열의 최대 길이가 할당될 것입니다.
반복문을 통해 증가하는 수열의 최대값을 구해줍니다.
arr[i]까지의 수열을 점검하여 arr[i]가 어느 수보다 크다면 dp[i][0]의 값을 비교하여 적절한 값을 할당합니다.
감소수열의 최대값은 인덱스를 거꾸로 마지막부터 0인덱스 순서로 진행합니다.
reverse를 사용해도 됩니다.
모두 할당된 dp에서 1을 빼주어야 바이토닉수열의 길이가 됩니다.
이유는 1, 2, 3, 4, 5 / 5, 3, 1 이런식으로 중복되는 수가 나오는데, 바이토닉수열은 1, 2, 3, 4, 5, 3, 1 과 같은 방식이기때문에 1을 빼줍니다.
