99클럽 코테 스터디 28일차 TIL / DP(다이나믹 프로그래밍)

✏️ 문제

[백준/BOJ] 11055번: 가장 큰 증가하는 부분 수열(https://www.acmicpc.net/problem/11055)

 

수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: solved.ac 기준 S2

✅ 소요 시간: 측정 X

✅ 권장 시간: 1시간 15분

 

💡 풀이

1) 문제 이해

어제 풀었던 가장 긴 감소하는 부분 수열 문제와 유사한 문제다. 최종 정답 코드가 어제 쓴 코드랑 크게 차이나는 건 아니지만 풀이 방법을 정리해보려고 한다.

 

2) 아이디어 흐름 및 코드

① DP 테이블 정의 및 초기값 채우기

N = int(input())

A = list(map(int, input().split()))

DP = A.copy()

 

• DP = A.copy()
  
  • DP 테이블의 각 인덱스는 ' A[i]를 마지막 원소로 하는 가장 큰 증가하는 부분 수열의 합'을 의미한다.
  • 증가하는 부분이 한 군데도 없는 경우가 있을 수 있기 때문에 DP 테이블의 초기 상태는 A와 동일하다.

 

② 점화식 유도

for i in range(N):
    for j in range(i):
        if A[i] > A[j] and A[i]+DP[j] > DP[i]:
            DP[i] = A[i]+DP[j]

 

• A[i] > A[j]
  • A[j]는 A[i] 이전 값을 의미하고 증가하는 부분 수열 형태를 맞춰주기 위해 이 조건이 필요하다.
• A[i]+DP[j] > DP[i]
  • DP[i]를 업데이트 하기 위해 A[j]를 마지막으로 하는 부분 수열에 DP[j]를 추가했을 때의 합이 기존 DP[i]보다 큰지 확인하는 조건이다.

 

3) 전체 코드

N = int(input())

A = list(map(int, input().split()))

DP = A.copy()

for i in range(N):
    for j in range(i):
        if A[i] > A[j] and A[i]+DP[j] > DP[i]:
            DP[i] = A[i]+DP[j]

print(max(DP))

 

4) 어려웠던 점/배운 점

🚨 어려웠던 점

• TIL에는 굉장히 금방 푼 것처럼 정리해뒀지만 A[i]+DP[j] > DP[i]를 끌어내는 데에 꽤나 오랜 시간이 걸렸다.
• 프린트문으로 중간 값 찍어가면서 한참 보고 있던 중에 우연히 저 조건을 발견하게 됨

❗ 배운 점

• 이제 DP 테이블을 어떻게 정의해야 할지가 아주 약간은 눈에 보이는 것 같다.