미소를뿌리는감자의 코딩
[백준 2024/03/23] 11053번 가장 긴 증가하는 부분 수열 본문
728x90
https://www.acmicpc.net/problem/11053
1. 접근 방법
처음에 접근을 잘못했다가 많이 헤맨 문제이다.
dp를 이용해서 문제를 풀어야 한다.
이때, dp란? : 최적 부분 구조와 중복되는 부분문제를 가지는 것이다.
중복되는 부분문제는 말그래도 중복되는 문제를 가지는 것이고, 최적 부분 구조는 문제를 해결하기 위한 최적의 방법은 문제를 구성하는 부분 문제들의 최적의 방법으로부터 구성될 수 있다고 하는 것이다.
이번 문제는 수열의 크기만큼 dp를 구성해서, 해당 인덱스 위치를 끝으로 하는 LIS의 최대 길이를 저장해 두었다. -> 처음에는 1로 초기화
이후, 2중 for문을 통해, 해당 인덱스의 이전 인덱스에서 현재 인덱스로 이동할 때의 값 비교를 통해서 더 큰 값을 인덱스에 저장해 두었다.
( 값이 증가하는 방식일 때만 비교해 주었다.)
2. 코드
def lis_length(nums):
if not nums:
return 0
# DP 테이블 초기화
dp = [1] * len(nums) # 각 위치를 끝으로 하는 LIS의 길이를 저장. 최소 길이는 1이므로 1로 초기화.
# 모든 위치에 대해 LIS 계산
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
# DP 테이블에서 최대 값을 찾음
return max(dp)
height = int(input())
# 입력 예시
nums = list(map(int, input().split()))
print(lis_length(nums))
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/03/27] 1300번 K번째 수 (0) | 2024.03.27 |
---|---|
[백준 2024/03/23] 11651번 좌표 정렬하기 2 (1) | 2024.03.23 |
[백준 2024/03/21] 1932번 정수 삼각형 (0) | 2024.03.21 |
[백준 2024/03/20] 9461번 파도반 수열 (0) | 2024.03.20 |
[백준 2024/03/19] 9184번 신나는 함수 실행 (0) | 2024.03.19 |