[백준/C++] 11053번_가장 긴 증가하는 부분 수열

문제는 다음과 같습니다.

먼저 전역배열 d[n]에 n번째 항까지 도달하였을 때의 가장 긴 증가 수열의 항의 수를 담자고 생각했습니다.

위의 예시를 그대로 빌려 보면,
10 20 10 30 20 50 에서

• 첫번째 경우는 10 -> d[1]=1 (자기 자신 하나)
• 두번째 경우는 10, 20 -> d[2]=2
• 세번째 경우는 10 -> d[3]=1
  ...

이렇게 나아갑니다.
여기서 봐야 할 것은
n번째 d[n]을 구하기 위해서는 앞의 1번부터 ~ n-1번째를 돌면서, (두번째 for문 안의 변수 j 참고)

우리가 구하는 것은 증가 수열이므로, 이 전의 a[j]<a[i]인 모든 j들에 대하여,
이들의 d[j]+1 (1은 현재 n 자기 자신을 더한 것)이 d[i]가 될 수 있는 모든 값들이다.

즉, j를 돌면서, 최댓값을 매번 비교하며 갱신해주면 된다.

이에 대한 로직은 다음 과정이다.

      cin>>tmp;
      a[i]=tmp;
      d[i]=1;

      for(int j=i-1; j>=1; j--){ // 앞에 항들 점검
        if(a[j]<a[i]){ // 항이 현재 항보다 작다면-> 증가 수열 조건 성립
          d[i]=max(d[i], d[j]+1); // d[i]가 될 수 있는 값들 중 최댓값 매번 갱신하기
        }
      }

가장 중요했던 부분은 이 부분인 것 같습니다.

처음에 문제가 잘 안풀렸던 부분은, 그저 a[j]의 값이 a[i]보다 작고, 그 중 가장 큰 a[j]만 구하면 d[i]는 d[j]+1 이라고 생각했었다.
하지만, 계속 오류가 났었고 생각해보니 가장 큰 a[j]를 구하는 것이 아닌 가장 큰 d[j]의 값을 갖고 있는 a[j]를 구하는 것이었다.

제 전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

int a[1001]={0, };
int d[1001]={0, };

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, tmp, res;
    cin>>n;
    cin>>tmp;
    a[1]=tmp;
    d[1]=1;
    res=1;

    for(int i=2; i<=n; i++){
      cin>>tmp;
      a[i]=tmp;
      d[i]=1;

      for(int j=i-1; j>=1; j--){
        if(a[j]<a[i]){
          d[i]=max(d[i], d[j]+1);
        }
      }

      res=max(res, d[i]);
    }

    cout<<res<<endl;
    return 0;
}

---

2월 8일 화요일 복습)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int a[1001]={0, }; int dp[1001]={0, };
    int tmp, len, res=1, n; cin>>n;
    
    for(int i=0; i<n; i++){
      cin>>tmp; a[i]=tmp; len=1;
      for(int j=i-1; j>=0; j--){
        if(a[j]<a[i] && dp[j]+1>len) len=dp[j]+1;
      }
      dp[i]=len;
      res=max(res, dp[i]); // 가장 긴 길이 계속해서 갱신
    }

    cout<<res<<"\n";
    return 0;
}