https://www.acmicpc.net/problem/11054
#Solution
가장 긴 수열 찾기 https://claude-u.tistory.com/184 참조.
순방향 한번, 역방향 한번으로 함수를 돌려준 뒤, 더해준다.
그 뒤 가장 긴 수열을 출력해주면 된다.
O(n^2)이 나올텐데 아직(?)은 시간 초과가 안나기에 쉬운 코드로 돌려주었다.
A = int(input())
A_list = list(map(int, input().split()))
result = [[] for _ in range(A)]
#순방향 돌려주기
for i in range(A):
if i == 0:
result[i].append(A_list[i])
else:
for j in range(0, i):
if result[j][-1] < A_list[i]: #이전 수열의 마지막 숫자가 나보다 작은가?
if len(result[i]) - 1 < len(result[j]): #수열의 길이가 현재값보다 작은가?
result[i] = result[j] + [A_list[i]]
if not result[i]:
result[i].append(A_list[i]) #자신이 지금까지 최소값일 경우
#역방향 돌려주기
A_list_reversed = list(reversed(A_list))
result_reversed = [[] for _ in range(A)]
for i in range(A):
if i == 0:
result_reversed[i].append(A_list_reversed[i])
else:
for j in range(0, i):
if result_reversed[j][-1] < A_list_reversed[i]:
if len(result_reversed[i]) - 1 < len(result_reversed[j]):
result_reversed[i] = result_reversed[j] + [A_list_reversed[i]]
if not result_reversed[i]:
result_reversed[i].append(A_list_reversed[i])
#합산해서 가장 큰 숫자 산출
answer = 0
for i in range(A):
answer = max(answer, len(result[i]) + len(result_reversed[-i-1]))
print(answer - 1) #가운데 숫자는 두 번 더해지므로 -1
'Programming [Python] > 백준 알고리즘 솔루션' 카테고리의 다른 글
#158 백준 파이썬 [9251] LCS (0) | 2019.10.28 |
---|---|
#157 백준 파이썬 [2565] 전깃줄 - LIS (1) | 2019.10.28 |
#155 백준 파이썬 [2156] 포도주 시식 - 점화식 (0) | 2019.10.27 |
#154 백준 파이썬 [10844] 쉬운 계단 수 (0) | 2019.10.27 |
#153 백준 파이썬 [2960] 에라토스테네스의 체 (0) | 2019.10.25 |