백준 11055번 [가장 큰 증가하는 부분 수열](C++) -yes6686- 티스토리

백준 문제 풀이: 11055 [가장 큰 증가하는 부분 수열]

---

문제 링크: https://www.acmicpc.net/problem/11055

문제 설명:

주어진 배열에서 증가하는 부분 수열의 합이 가장 큰 값을 구하는 문제입니다. 부분 수열은 배열의 원소 순서를 유지해야 합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

int arr[1001]; // 입력된 배열
int dp[1001];  // dp[i]: i번째 원소를 마지막으로 하는 증가하는 부분 수열의 최대 합

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        dp[i] = arr[i]; // 초기화: 각 원소 자체가 최대 합
    }

    int ans = arr[0];

    // 최대 합 계산
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) { // 증가 조건
                dp[i] = max(dp[i], dp[j] + arr[i]); // 최대 합 갱신
            }
        }
        ans = max(ans, dp[i]); // 전체 최대값 갱신
    }

    cout << ans << '\n';
    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍을 사용하여 각 위치를 마지막 원소로 하는 증가하는 부분 수열의 최대 합을 계산합니다.
• 구현 세부사항:
  • dp[i]: 배열의 i번째 원소를 마지막 원소로 하는 증가하는 부분 수열의 최대 합
  • 점화식: dp[i] = max(dp[i], dp[j] + arr[i]) (j < i이고 arr[j] < arr[i]일 때)
  • 전체 최대 합은 dp 배열의 최댓값
• 시간 복잡도 분석: O(n²)
  • 이중 루프를 통해 각 원소에 대해 이전 원소를 확인

---

결과

가장 큰 증가하는 부분 수열의 합을 정확히 계산합니다. 동적 프로그래밍을 활용하여 효율적으로 문제를 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!