Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- Spring
- JPA
- Kotlin
- 백준
- 백준 16719
- 프로래머스
- 웹어플리케이션 서버
- 백준 15685
- MSA
- 프로그래머스
- 백준 파이썬
- sql 기술면접
- MySQL
- 백준 17779
- Coroutine
- 백준 17626
- 백준 19238
- java 기술면접
- 파이썬
- 백준 16236
- java
- JVM
- 백준 16235
- spring cloud
- Spring Boot
- with recursive
- re.split
- springboot
- spring oauth
- spring security
Archives
- Today
- Total
시작이 반
[백준] 11054번(python 파이썬) 본문
SMALL
dp1
리스트 A의 i : 0 ~ n-1 에서의 증가하는 수열의 값을 구한다.
dp2
리스트 A의 i : n-1 ~ 0 에서의 증가하는 수열의 값을 구한다.
ex)
dp3
dp3[0] = dp2[0]
dp3[n-1] = dp1[n-1]
리스트 A의 i :1 ~ n-2 에서
1. 리스트 A의 j : 1 ~ i 부분에서 a[i] 보다 작은 값중에서 최대값 dp1[j] 을 찾는다.
2. 리스트 A의 j : i ~ n-2 부분에서 a[i] 보다 작은 값중에서 최대값 dp2[j] 을 찾는다.
dp3[i] = 1번과 2번을 더한후 1을 더해준다.
n = int(input())
a = list(map(int, input().split()))
reverse_a = list(reversed(a))
inc_dp = [0] * n
dec_dp = [0] * n
dp = [0] * n
def incSequence():
inc_dp[0] = 1
for i in range(1, n):
max_temp = 0
for j in range(i):
if a[i] > a[j]:
max_temp = max(max_temp, inc_dp[j])
inc_dp[i] = max_temp + 1
def decSequence():
dec_dp[0] = 1
for i in range(1, n):
max_temp = 0
for j in range(i):
if reverse_a[i] > reverse_a[j]:
max_temp = max(max_temp, dec_dp[j])
dec_dp[i] = max_temp + 1
def bitonic():
for i in range(n):
max_left_temp = 0
max_right_temp = 0
if i == 0:
dp[i] = dec_dp[i]
continue
if i == n-1:
dp[i] = inc_dp[i]
continue
for j in range(i):
if a[i] > a[j]:
max_left_temp = max(max_left_temp, inc_dp[j])
for k in range(i+1, n):
if a[i] > a[k]:
max_right_temp = max(max_right_temp, dec_dp[k])
dp[i] = max_left_temp + max_right_temp + 1
incSequence()
decSequence()
dec_dp.reverse()
bitonic()
print(max(dp))
LIST
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 2565번(python 파이썬) (0) | 2021.02.25 |
---|---|
[백준] 11053번(python 파이썬) (0) | 2021.02.24 |
[백준] 11055번(python 파이썬) (0) | 2021.02.09 |
[백준] 2156번(python 파이썬) (0) | 2021.02.09 |
[백준] 1463번(python 파이썬) (0) | 2021.02.08 |