-
백준 파이썬 11722번 : 가장 긴 감소하는 부분 수열 풀이기타/알고리즘 2020. 12. 25. 10:54반응형
11722번: 가장 긴 감소하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}
www.acmicpc.net
nums 안의 수에 대해 가장 긴 감소하는 부분 수열의 길이를 구하는 문제다.
- 앞의 수가 다음 수보다 크다면 문제의 조건을 만족한다
- 각 인덱스에 대해 자신보다 인덱스가 작은 값을 검색하여 조건을 만족하는 수의 개수를 찾는다
- 앞의 인덱스에서 조건을 만족하는 수의 개수를 찾으면, 다음 계산시에 이를 이용해준다.
예제로 주어진 nums = [10, 30, 10, 20, 20, 10]로 생각해보면
- dp[i]에 인덱스 i까지의 '가장 긴 감소하는 부분 수열의 길이'를 저장한다
- nums[i]에 대해 자신 이전에 오는 값들을 탐색한다.이 값들을 nums[j]라고 하면
- nums[j] > nums[i] 일 때 문제의 조건을 만족한다
- 조건을 만족하는 수의 개수를 dp[i]로 저장하려고 한다
- 만약 nums[i]가 문제의 조건을 만족한다면 이전의 최대값인 dp[j]에 1을 더한 값이 dp[i]가 될 것이다
- nums[i]가 조건을 만족하지 못한다면, dp[i]는 이전의 값 그대로인 dp[i]가 될 것이다
- 예를 들어 nums[3] = 20이라면
- nums[2] = 10이므로 조건을 만족하지 못한다
- i = 3까지의 최대 길이는 2이므로 dp[3] = 2다
n = int(input()) nums = list(map(int, input().split())) dp = [1 for i in range(n)] for i in range(n): for j in range(i): if nums[j] > nums[i]: dp[i] = max(dp[i],dp[j]+1) print(max(dp))
반응형'기타 > 알고리즘' 카테고리의 다른 글
백준 파이썬 9417번 - 최대GCD (0) 2021.06.27 백준 파이썬 15486 : 퇴사 2 풀이 (0) 2020.12.26 [파이썬] 리트코드 198. House Robber 풀이 (0) 2020.12.24 [파이썬] 리트코드 39. Combination Sum 풀이 (0) 2020.12.24 [파이썬] 리트코드 53. Maximum Subarray 풀이 (0) 2020.12.24