99클럽 코테 스터디 28일차 TIL - DP(백준11055-가장 큰 증가하는 부분 수열 )

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

• 오늘의 학습 키워드 : DP
• 공부한 내용

예시로

작동 과정 예시 (입력: 10, [1, 100, 2, 50, 60, 3, 5, 6, 7, 8])

• 초기 dp = [1, 100, 2, 50, 60, 3, 5, 6, 7, 8]
• 루프 동작:
  • i=1: dp[1] = max(dp[1], dp[0] + A[1]) → 101
  • i=3: dp[3] = max(dp[3], dp[0] + A[3], dp[2] + A[3]) → 51
  • ...
  • i=9: dp[9] = max(dp[9], dp[6] + A[9], ..., dp[8] + A[9]) → 113
• 최종 dp = [1, 101, 2, 51, 111, 6, 11, 17, 24, 113]
• 결과: max(dp) = 113

1. dp[i]는 i번째 요소로 끝나는 최대 합을 저장한다.
2. A[j] < A[i] 조건을 확인하며 이전 값들의 최대 합을 재활용한다.
3. 모든 요소를 처리한 후, max(dp)로 결과를 구한다.

 

🎯 DP 풀이

import sys

# 입력 받기: 수열의 길이 N과 수열 A
N = int(sys.stdin.readline().strip())  # 수열의 길이
A = list(map(int, sys.stdin.readline().strip().split()))  # 수열

# dp 배열 초기화: dp[i]는 A[i]를 마지막으로 하는 최대 합 증가 부분 수열의 합
dp = A.copy()  # 각 요소는 초기값으로 자기 자신을 포함한 부분 수열의 합

# 반복문을 통해 dp 배열 계산
for i in range(1, N):  # i는 현재 위치 (A[i]를 마지막으로 고려)
    for j in range(i):  # j는 i 이전의 모든 위치를 탐색
        if A[j] < A[i]:  # 증가 조건: A[j]가 A[i]보다 작아야 증가 수열
            # dp[i]를 갱신: 이전 최대 합(dp[j])에 A[i]를 추가한 값과 기존 dp[i] 중 큰 값 선택
            dp[i] = max(dp[i], dp[j] + A[i])

# dp 배열에서 가장 큰 값이 답: 최대 합 증가 부분 수열의 합
print(max(dp))

 

• 오늘의 공부 회고
  • dp는 아직까지는 풀수 있을정도..? 실버정도는 그래도 풀수있을것 같다..