[11055]가장 큰 증가하는 부분 수열- C++

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

11055번: 가장 큰 증가하는 부분 수열

나에게는 정말 어려웠던 문제다 1시간 정도 고민하고 감도 잡히질 않아 답을 보았다.

---

풀이

배열 두 개를 만든다. 원본 배열, 테이블이다.

int arr[1005];
int dp[1005];

답에서는 한 번씩 다 돌아가면서 체크하는 방식을 알려줬다.

그림으로 설명해보겠다

이중 for문을 사용하여 i에 대하여 나보다 작은 수이면 더하고 본다

for(int i = 1; i <= n; ++i)

    for(int j = 1; j < i; ++j)

      if(arr[i] > arr[j]) dp[i] = max(dp[i], dp[j] + arr[i]);

---

CODE

#include <bits/stdc++.h>

using namespace std;

void init(){

  ios_base::sync_with_stdio(false);

  cin.tie(0);

  cout.tie(0);

}

int n;

int arr[1005];

int dp[1005];

int main(){

  init();

  cin >> n;

  for(int i = 1; i <= n; ++i){

    cin >> arr[i];

    dp[i] = arr[i];

  }

 

  for(int i = 1; i <= n; ++i)

    for(int j = 1; j < i; ++j)

      if(arr[i] > arr[j]) dp[i] = max(dp[i], dp[j] + arr[i]);

  cout << *max_element(dp+1, dp+n+1);

 

  return 0;

}

---

문제를 풀며

뭔가 할 수 있다고 생각했는데 어떻게 풀어야 할지 감도 오지 않았다.

답을 보고 난 후 맞추는 방식은 나를 너무 힘들게 한다. 내가 해낸 게 아닌데 맞았습니다!라고 뜨는 걸 보면 신난다기보다 왜인지 모를 죄책감이 든다.

모르는 건 아이디어를 배운다는 마인드로 임해 왔지만 요즘 DP문제를 풀면서 나 혼자 해결하기보단 답에 의존하는게 더 많다 보니 너무 스트레스이다....

과연 나중에는 이렇게 배운 아이디어들로 혼자서 문제들을 풀 수 있을까? 에 대한 고민을 많이 하는 중인데 과연 내가 옳은 방향으로 가고 있는 걸까?