230130 Do-while이 없는 파이썬, while보다 빠른 for

# 14002 1699 2225 1149 1309 11057 9465 1932 11055 11722

 

# task 

 

num = int(input())

seq = [int(i) for i in input().split()]

dp = [1]*num # 0부터 5까지 6개의 원소
tracker = [-1]*num

for i in range(1,num): #1부터 5까지 5개의 원소
	for j in range(0,i):
		if seq[j]<seq[i] and dp[j]>=dp[i]:
			dp[i] = dp[j]+1
			tracker[i]= j

max_value = max(dp) # 어레이에서 가장 큰 값
idx = dp.index(max_value) 


print(max_value)
answer=[]

while True:
	
	answer.append(seq[idx])
	
	if tracker[idx]==-1:
		break
	else:
		idx = tracker[idx]

answer.reverse()

print(' '.join(str(i) for i in answer))

 

# 1699

# 입력
num = int(input())

if num<=3:
	print(num)
	exit()


# 초기값 설정
dp = [-1]*(num+1)
dp[0] = 0
dp[1] = 1
dp[2] = 2

#
for i in range(3,num+1):
	dp[i] = i
	j=1
	idx = i-1
	while idx>=0:
		idx = i-j*j
		if dp[idx] !=-1:
			if dp[idx]+1 < dp[i]:
				dp[i] = dp[idx] + 1
		j += 1

print(dp[num])

# 1699 2225 1149 1309 11057 9465 1932 11055 11722


import math

# 입력
num = int(input())

if num<=3:
	print(num)
	exit()


# 초기값 설정
dp = [-1]*(num+1)
dp[0] = 0

# DP
for i in range(1,num+1):
	dp[i] = i
	maxroot = int(math.sqrt(i))
	for j in range(1,maxroot+1):
		idx = i-j*j
		if dp[idx]!=-1:
			if dp[idx]+1<dp[i]:
				dp[i] = dp[idx]+1
			

print(dp[num])

 

 

 

# 2225

 

#2225

import math
# 입력 k개의 정수를 더하여 n을 만들어라.
n,k = map(int,input().split())

# x개의 정수로 만들 수 있는 y의 원소를 a[x][y]라고 할 때 담아야할 것들
a = [([-1]*(n+1))]*(k+1)

# 1개의 정수로 만들 수 있는 0~n의 방법수는 각각 1개
a[0] = [1]+[0]*n
a[1] = [1]*(n+1)

 
# 6개의 정수로 만들수 있는 3의 방법수는 
# 5개의 정수로 만들 수 있는 0부터 3까지의 방법수를 더한 것과 같다.
for i in range(2,k+1):
	list = []
	for j in range(n+1):
		list.append(sum(a[i-1][0:j+1]))
	a[i] = list[:]
		
print(a[-1][-1]%1000000000)

 

# 11054 

 

두 리스트의 원소간의 합을 나타내는 방식

 

import sys

num  = int(input())
sequence = [int(i) for i in sys.stdin.readline().rstrip().split()]
dp = [1]*num

# 먼저 i로 끝나는 증가수열의 길이를 찾고.
for i in range(num):
    present_number = sequence[i]
    dp[i] = 1
    for j in range(i):
        if sequence[j]<sequence[i]:
            if dp[i]<dp[j]+1:
                dp[i] = dp[j]+1

#print(dp)

# (X)먼저 i로 시작하는 감소수열의 길이를 찾는다. 
# => 그냥 시퀀스를 뒤집어서 위와 똑같이 i로 끝나는 증가수열을 찾는다
sequence.reverse()

dp2 = [1]*num
for i in range(num):
    present_number = sequence[i]
    dp2[i] = 1
    for j in range(i):
        if sequence[j]<sequence[i]:
            if dp2[i]<dp2[j]+1:
                dp2[i] = dp2[j]+1
dp2.reverse()
#print(dp2)


# 둘의 더한 후 -1을 하고 출력해준다.



print(max( [ x+y for x,y in zip(dp,dp2)] )-1 )