취준생의 코딩테스트 연습기

[백준] 11053번 가장 긴 증가하는 부분 수열 / 파이썬(python) 본문

코딩테스트/백준

[백준] 11053번 가장 긴 증가하는 부분 수열 / 파이썬(python)

Jiwon_C 2021. 5. 23. 23:18

# 문제 링크

https://www.acmicpc.net/problem/11053

 

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

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

www.acmicpc.net

# Soultion

1
2
3
4
5
6
7
8
9
10
11
n = int(input())
arr = list(map(int,input().split()))
 
length = [1]*n
 
for i in range(1,n):
    for j in range(i-1,-1,-1):
        if arr[j]<arr[i]:
            length[i] = max(length[j]+1,length[i])
            
print(max(length))
 cs
 

4. 각각의 숫자들은 길이가1인 수열이므로 1로 초기화해준다.

6. 2번째 숫자부터 n까지 한개씩 비교해준다.

8. 수열의 값이 현재 비교할 값보다 작은경우에만 길이를 저장해준다.

 

'코딩테스트 > 백준' 카테고리의 다른 글

[백준] 11724번 연결 요소의 개수 / 파이썬(python)  (0) 2021.05.25
[백준] 1654번 랜선 자르기 / 파이썬(python)  (0) 2021.05.25
[백준] 1463번 1로 만들기 / 파이썬(python)  (0) 2021.05.23
[백준] 1149번 RGB거리 / 파이썬(python)  (0) 2021.05.23
[백준] 10816번 숫자 카드 2 / 파이썬(python)  (0) 2021.05.21
'코딩테스트/백준' Related Articles more
Comments