[백준] 11053, 14002, 1912, 1699 (파이썬)

어제 글을 작성하는 것을 잊어버렸다. 앞으로는 끝나자마자 바로바로 적는 습관을 들여야할 것 같다. 오늘은 다이나믹 프로그래밍 예제를 이어서 풀어나갔다. 요즘 막히는 빈도가 늘어나서 찾아보니 문제를 많이 풀어보는 것이 답이라고 한다. 그래도 이 후에 여러 유형들을 풀어볼 것을 생각해서 교재를 하나 구입했다. 이코테라는 책인데 배송되면 틈틈히 공부한 것을 같이 올려볼 계획이다.

백준 11053번 가장 긴 증가하는 부분 수열

# dp문제의 대표문제라고 한다. 아직도 헤매는 중
import sys
size = int(sys.stdin.readline())
A = list(map(int,sys.stdin.readline().split()))
# 자신을 포함하여 만들수 있는 부분 수열 크기
dp = [0 for _ in range(size)]
for i in range(size):
    for j in range(i): 
        if A[i]>A[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1
print(max(dp))

백준 14002번 가장 긴 증가하는 부분 수열 4

'''순서를 신경쓰지 못함, 역순으로 진행하면 해결
import sys
size = int(sys.stdin.readline())
A = list(map(int,sys.stdin.readline().split()))
dp = [0 for _ in range(size)]
for i in range(size):
    for j in range(i): 
        if A[i]>A[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1
dp2 = list()
for k in range(1,max(dp)+1):
    dp2.append(A[dp.index(k)])
print(max(dp))
print(*dp2)
'''
import sys
size = int(sys.stdin.readline())
A = list(map(int,sys.stdin.readline().split()))
dp = [0 for _ in range(size)]
dp2 = list()
for i in range(size):
    for j in range(i): 
        if A[i]>A[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1
count = max(dp)
for k in range(size-1,-1,-1):
    if dp[k] == count:
        dp2.append(A[k])
        count-=1
dp2.reverse()
print(max(dp))
print(*dp2)

백준 1912번 연속합

import sys
size = int(sys.stdin.readline())
n = list(map(int,sys.stdin.readline().split()))
dp = list()
dp.append(n[0])
for i in range(1,len(n)):
    dp.append(max(dp[i-1]+n[i],n[i]))
print(max(dp))

백준 1699번 제곱수의 합

# 점화식은 알고리즘을 참고했다.
# dp[i] = min(dp[i - j]) + 1
# 아직까지 패턴 파악에 걸리는 시간이 오락가락하다.
import sys
N = int(sys.stdin.readline())
dp = [0 for _ in range(N + 1)]
square = [k*k for k in range(1, 317)]
for i in range(1,N+1):
    count = list()
    for j in square:
        if j>i:
            break
        count.append(dp[i - j])
    dp[i] = min(count) + 1
print(dp[N])