๋ฌธ์
https://www.acmicpc.net/problem/11054
๋ฐฑ์ค ๋จ๊ณ๋ณ ํ์ด - ๋์ ๊ณํ๋ฒ 1
ํ์ด
์์ด S๊ฐ ์ด๋ค ์ Sk๋ฅผ ๊ธฐ์ค์ผ๋ก S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN์ ๋ง์กฑํ๋ค๋ฉด, ๊ทธ ์์ด์ ๋ฐ์ดํ ๋ ์์ด์ด๋ผ๊ณ ํ๋ค.
์ฆ, ์์ด์์ ์ด๋ ํ ์ง์ ์ P๋ผ๊ณ ํ์๋ (์ฆ๊ฐํ๋ ์์ด), P, (๊ฐ์ํ๋ ์์ด)ํํ๊ฐ ๋์ด์ผ ํ๋ค.
์ํ, ์ดํด๋ ์ฝ์ง๋ง... ๊ตฌํ์ด ์ด๋ ต๋ค!
๊ฒฐ๊ตญ ๊ตฌ๊ธ๋ง, AI๋ฅผ ํตํด ํ์ด๋ฅผ ์ป์ด๋๋ค.
์ฐพ์๋ณด๋ ๋ฐ์ดํ ๋ ์์ด์ ๊ตฌํ๋ ๊ณต์์ ์๋์ ๊ฐ๋ค.
๋ฐ์ดํ ๋ ์์ด = LIS(์ฆ๊ฐ๋ถ๋ถ์์ด) + LDS(๊ฐ์๋ถ๋ถ์์ด) - 1
ํ์ง๋ง ์ฐ๋ฆฌ๋ ์ ํ์ ์ด ๋๋ ์ง์ ์ ๋ชจ๋ฅด๋ ์ํ๋ค.
๋ฌด์กฐ๊ฑด LIS, LDS๋ฅผ ๊ตฌํ๋๊ฒ ์๋๋ผ ์์ด ํ๋ํ๋๋ฅผ ์ ํ์ ์ผ๋ก ๊ฐ์ ํ๊ณ ๋ฐ์ ธ๋ด์ผํ๋ค.
์์ ๋ฐ์ดํฐ๋ก ์ดํด๋ณด๋ฉด,{1 5 2 1 4 3 4 5 2 1}์์ ๊ฐ์ฅ ๋ฐ์ดํ ๋ ์์ด์ {1 2 3 4 5 2 1}, ๊ธธ์ด๋ 7์ด๋ค.
์ด๊ฑด ๋ค์์ ์ธ๋ฒ์งธ์ 5๋ฅผ ์ ํ์ ์ผ๋ก ์ผ์์๋์ LIS+LDS-1 ๊ฐ์ด๋ค.
์ ๋ต ์ฝ๋๋ ์๋์ ๊ฐ๋ค.
# ๋ฉ๋ชจ๋ฆฌ: 31252KB / ์๊ฐ: 100ms
from sys import stdin
input = stdin.readline
N = int(input())
A = list(map(int, input().split()))
def bitonic():
lis = [1] * N
lds = [1] * N
for i in range(1, N): # LIS
for j in range(i):
if A[i] > A[j] and lis[i] < lis[j] + 1:
lis[i] = lis[j] + 1
for i in range(N-2, -1, -1): # LDS
for j in range(N-1, i, -1):
if A[i] > A[j] and lds[i] < lds[j] + 1:
lds[i] = lds[j] + 1
max_length = 0
for i in range(N):
max_length = max(max_length, lis[i] + lds[i] - 1)
return max_length
print(bitonic())
1. ์ ๋ ฅ๊ฐ ํ ๋น
from sys import stdin
input = stdin.readline
N = int(input())
A = list(map(int, input().split()))
2. ๋ถ๋ถ ์์ด์ ๊ตฌํ ํจ์ ์์ฑ
def bitonic():
lis = [1] * N
lds = [1] * N
for i in range(1, N): # LIS
for j in range(i):
if A[i] > A[j] and lis[i] < lis[j] + 1:
lis[i] = lis[j] + 1
for i in range(N-2, -1, -1): # LDS
for j in range(N-1, i, -1):
if A[i] > A[j] and lds[i] < lds[j] + 1:
lds[i] = lds[j] + 1
lis์ lds์ 1๋ก ์ด๋ฃจ์ด์ง N๋งํผ์ ๋ฆฌ์คํธ๋ฅผ ํ ๋นํด์คฌ๋ค.
๊ฐ ์ธ๋ฑ์ค๊ฐ์ i๋ฒ์งธ ์์๊น์ง์ LIS, LDS ๊ฐ์ ๋ปํ๋ค.
์ฒซ๋ฒ์งธ for๋ฌธ์ผ๋ก LIS๋ฅผ ๊ตฌํ๊ณ , ๋๋ฒ์งธ for๋ฌธ์ผ๋ก LDS๋ฅผ ๊ตฌํด์ค๋ค.
i๋ 1๋ถํฐ N-1๋ฒ์งธ ์ธ๋ฑ์ค๋ฅผ, j๋ i์ด์ ๊น์ง์ ์ธ๋ฑ์ค๋ฅผ ํ์ํ๋ค.
๋ง์ฝ A์ i๋ฒ์งธ ์ธ๋ฑ์ค๊ฐ > j๋ฒ์งธ ์ธ๋ฑ์ค๊ฐ์ด๊ณ , i์ ํ์ฌ LIS๊ฐ๋ณด๋ค j์ LIS๊ฐ+1์ด ๋ ํฌ๋ค๋ฉด lis[j]+1๋ก ๋ณ๊ฒฝํ๋ค.
์์ ๋ฐ์ดํฐ๋ก ์ดํด๋ณด์.A = [1, 5, 2, 1, 4]์ด๊ณ , lis = [1, 1, 1, 1, 1]์ผ๋์ ๊ณผ์ ์ด๋ค.
๋จผ์ i = 1์ผ๋ j = 0๋ง ๊ฐ๋ฅํ๋ค.
A[i]๋ 5, A[j]๋ 1์ด๋ฏ๋ก ์ฒซ๋ฒ์งธ ์กฐ๊ฑด์ ๋ง์กฑํ๋ค.
lis[i]๋ 1, lis[j]๋ 1์ด๋ฏ๋ก lis[i] < lis[j] + 1 ์กฐ๊ฑด๋ ๋ง์กฑํ๋ค.
๋ฐ๋ผ์ lis[i]๊ฐ์ 2๋ก ์ค์ ํ๋ค. lis = [1, 2, 1, 1, 1]
i = 2์ผ๋, j = 0, 1 ์ด๋ค.
A[i]๋ 2, A[j]๋ ๊ฐ๊ฐ 1, 5์ด๋ฏ๋ก j๊ฐ 1์ผ๋ ์ฒซ๋ฒ์งธ ์กฐ๊ฑด์ ๋ง์กฑํ๋ค.
lis[i]๋ 1, lis[j]์ 2์ด๋ฏ๋ก lis[i] < lis[j] + 1 ์กฐ๊ฑด๋ ๋ง์กฑ.lis = [1, 2, 3, 1, 1]
...
์ด๋ฐ์์ผ๋ก ์งํํ๋ฉฐ LIS๊ฐ์ ๊ตฌํด์ค๋ค.
๋ค์์ LDS์ธ๋ฐ, ๊ทธ๋ฅ ๋ค์์๋ถํฐ LIS๋ฅผ ๊ตฌํ๋ ๋ฐฉ์์ผ๋ก ์์ฑํ๋ค.
์ฆ๊ฐ์์ด์ ๋ค์ง์ผ๋ฉด ๊ฐ์์์ด์ด ๋๋ฏ๋ก ์๊ด์๋ค.
i๋ N-2๋ฒ์งธ ์ธ๋ฑ์ค(๋ค์์ 2๋ฒ์งธ)๋ถํฐ 0๋ฒ์งธ ์ธ๋ฑ์ค๊น์ง 1์ฉ ์ค์ด๋ ๋ค.
๊ณผ์ ์ ์์ ๊ฐ๋ค.
max_length = 0
for i in range(N):
max_length = max(max_length, lis[i] + lds[i] - 1)
return max_length
LIS, LDS๋ฅผ ๊ตฌํ์ผ๋ฉด ์ต๋ ๋ฐ์ดํ ๋ ์์ด์ ๊ตฌํด์ค ์ฐจ๋ก๋ค.
์ต๋๊ฐ(=๊ฒฐ๊ณผ๊ฐ)์ ๋ฃ์ด์ค ํจ์ max_length๋ฅผ ์ ์ธํ๊ณ 0์ ํ ๋นํด์ค๋ค.(๋๋ float("-inf"))
0๋ถํฐ N-1๊น์ง ๋ชจ๋ ์ธ๋ฑ์ค๋ฅผ ์ํํ๋ฉฐ,
ํ์ฌ๊น์ง์ max_length๊ฐ๊ณผ ๋ฐ์ดํ ๋ ์์ด ๊ณต์(lis + lds - 1)์ ๋์
ํ ๊ฐ์ ๋น๊ตํ๋ค.
๋ชจ๋ ๋น๊ต๋ฅผ ๋ง์น๊ณ ์ต๋๊ฐ์ returnํ๋ค.
3. ๊ฒฐ๊ณผ ์ถ๋ ฅ
print(bitonic())
์ ํจ์๋ฅผ ์คํํ ๊ฒฐ๊ณผ๋ฅผ ๊ทธ๋๋ก ์ถ๋ ฅํ๋ค.
return๊ฐ์ผ๋ก max_length, ์ต๋๊ฐ์ด ๋ฐํ๋๋ฏ๋ก ๊ทธ๋๋ก ์คํ+์ถ๋ ฅ ํด์ฃผ๋ฉด ๋๋ค.