«   2022/05   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        
Archives
Today
11
Total
83,907
관리 메뉴

차근차근

[백준 11053] 가장 긴 증가하는 부분 수열 본문

Algorithm (Python)/DP

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

SWKo 2020. 9. 12. 01:58

0. 제목

  • 백준 11053 가장 긴 증가하는 부분 수열
  • BOJ 11053 가장 긴 증가하는 부분 수열
  • 파이썬 11053 가장 긴 증가하는 부분 수열
  • Python 11053 가장 긴 증가하는 부분 수열

1. 문제

www.acmicpc.net/problem/11053

 

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net


2. 풀이

  • dp[i] : i 번째 원소까지의 가장 긴 증가하는 부분 수열의 길이
  • 가장 먼저 dp의 원소들을 1로 초기화 시켜준다.
  • 문제에서 주어진 arr = {10, 20, 10, 30, 20, 50} 에서 dp[0] = 1, dp[1] = 2, dp[2] = 1 이고 초기값이 1인 dp[3]을 구하고자 할 때, arr[3]인 30이 arr[0]인 10보다 크므로 max(1, dp[0]+1) = 2, 30이 arr[1]인 20보다 크므로 max(2, dp[1]+1) = 3, 30이 arr[2]인 10보다 크므로 max(3, dp[2]+1) = max(3, 2) = 3 이다. 
  • 위와 같은 방법으로 dp 배열의 원소 값을 모두 구한 후 최대값을 출력해주면 된다.

 


3. 코드

1
2
3
4
5
6
7
8
9
10
= int(input())
dp = [1]*1001
array = list(map(int, input().split()))
 
for i in range(1, n):
    for j in range(0, i):
        if(array[i] > array[j]):
            dp[i] = max(dp[i], dp[j] + 1)
 
print(max(dp))

 

'Algorithm (Python) > DP' 카테고리의 다른 글

[백준 1495] 기타리스트  (0) 2020.09.13
[백준 9251] LCS  (0) 2020.09.12
[백준 11053] 가장 긴 증가하는 부분 수열  (0) 2020.09.12
[백준 12865] 평범한 배낭  (0) 2020.09.11
[백준 1904] 01타일  (0) 2020.09.10
0 Comments
댓글쓰기 폼