[python 파이썬] 백준 1965번 상자넣기

1965번: 상자넣기

 

메모이제이션과 점화식 그리고 max를 사용하면 되겠거니 했는데 max를 어떻게 적용해야할지 떠올리지못했다. 그리고 for문은 왜 하나만 쓰는거에 꽂혀서 이중포문으로 생각을 안했다. 

 

첫번째 풀이 - 틀림

dp를 초기화하고 상자에 들어갈수있다면 1씩 늘려줬는데 1씩 늘려서 그런지 느릴 것이고 그래서 틀린 것 같다. 

n = int(input())

box = list(map(int,input().split()))

dp=[0]*1001

for i in range(n):
  for j in range(i):
    if box[j]<box[i]:
      dp[i]+=1
print(max(dp))

 

두번째 풀이 - 정답 

포문 두개와 max를 사용한 방법! 익히자 

n = int(input())

box = list(map(int,input().split()))

dp=[1 for _ in range(n)]


for i in range(1,n):
  for j in range(i):
    if box[i]>box[j]:
      dp[i]=max(dp[i],dp[j]+1)

print(max(dp))