백준 1965 - 상자넣기 & 11053 - 가장 긴 증가하는 부분 수열

상자넣기

가장 긴 증가하는 부분 수열

알고리즘 분류)

• 다이나믹 프로그래밍

풀이

두 문제는 번호와 설명은 다르지만 실제로 구현해야 하는 코드는 똑같은 문제이다

일단은 원소1을 가진 dp 배열을 N횟수 만큼 만들어 준다
ex) N:6 ===> dp[1,1,1,1,1,1]
이 dp배열에는 각 부분에서 증가한 길이가 들어갈 것이다
가장 큰 증가하는 부분을 구하여야 하는데 아무리 짧아도 자기자신은 포함되니 1부터 시작한다
그다음 반복문을 통해 원소를 확인하여
현재 원소(i)가 0번째~i-1번째 원소보다 크다면 카운트를 1씩 증가시켜 누적되어 간다고 생각하면 편하다

ex) N:6 ===> [10, 20, 10, 30, 20, 50] 일 경우

• step1)
  i=0 , 비교할 대상이 없으니
  dp=[1,1,1,1,1,1]이다
  
  
• step2) i=1 , 10<20을 만족하니 ( dp[0]=1의 값+1=2 or 현재자신의값=1 ) 중 큰값을 선택 한다
  dp=[1,2,1,1,1,1]
  
  
• step3) i=2 , 10<10을 만족하지 않으니 넘어간다
  20<10을 만족하지 않으니 넘어간다
  dp=[1,2,1,1,1,1]
  
  
• step4) i=3 , 10<30을 만족하니 ( dp[0]=1의 값+1=2 or 현재자신의값=1 ) 중 큰값을 선택한다
  , 20<30을 만족하니 ( dp[1]=2의 값+1=3 or 현재자신의값=2 ) 중 큰값을 선택한다
  , 10<30을 만족하니 ( dp[2]=1의 값+1=2 or 현재자신의값=3 ) 중 큰값을 선택한다
  dp=[1,2,1,3,1,1]
  
  
• step5) i=4 , 10<20을 만족하니 ( dp[0]=1의 값+1=2 or 현재자신의값=1 ) 중 큰값을 선택한다
  , 20<20을 만족하지 않으니 넘어간다
  , 10<20을 만족하니 ( dp[2]=1의 값+1=2 or 현재자신의값=2 ) 중 큰값을 선택한다 (같음)
  , 30<20을 만족하지 않으니 넘어간다
  dp=[1,2,1,3,2,1]
  
  
• step6) i=5 , 위와 동일한 과정을 거치면
  dp=[1,2,1,3,2,4] 의 값이 들어있게 되고
  가장 큰 값인 '4'가 정답이다

소스코드

python)

N = int(input())
array = list(map(int,input().split()))
dp = [1]*N

for i in range(N):
    for j in range(i):
        if array[j] < array[i]:
            dp[i] = max(dp[j]+1,dp[i])
print(max(dp))