(C++, Python3) - 백준(BOJ) 11055번 :가장 큰 증가 부분 수열 답

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

dp문제였습니다.

📕 풀이방법

📔 입력 및 초기화

배열길이 n과 배열을 arr를 선언 후 입력받습니다.

📔 풀이과정

완전 탐색으로 i까지 도달했을 때 가장 큰 증가 부분 수열의 값을 d[i]라 하면 다음과 같은 점화식이 가능합니다.

 

$${ if \ arr[i] > arr[j] \ D[i] = MAX(D[j](0<=j<i) + A[i]) }$$ 

arr[i]가 가장 큰 값이므로 그보다 작은 arr[j]를 발견할 경우 그때의 D[j]값에서 현재 선택 값인 arr[i]를 더한 값의 최댓값을 d[i]에 저장하면 됩니다.

 

n이 1000까지이므로 O(N^2)로 동작 가능한 풀이입니다.

📔 정답 출력 | 반환

정답 배열의 가장 큰 원소를 반환합니다.

---

📕 Code

📔 C++

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> arr(n);
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }

  vector<int> dp(n);
  for (int i = 0; i < n; i++) {
    dp[i] = arr[i];
    for (int j = 0; j < i; j++) {
        if (arr[j] < arr[i]) {
            dp[i] = max(dp[i], dp[j] + arr[i]);
        }
    }
  }

  int ans = *max_element(dp.begin(), dp.end());
  cout << ans << '\n';
}

📔 Python3

import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
dp = [0] * n
dp[0] = arr[0]
for i in range(1,n):
    dp[i] = arr[i]
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j] + arr[i])
print(max(dp))

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.