백준 11054 C++

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

int n;
int arr[1010];
int dp[1010][2];           //first = index, second [0] = 현재 위치가 가장 낮은 지점일 때의 수, [1] = 현재가 가장 높은 지점일 떄의 수.

int main() {
      ios_base::sync_with_stdio(0);
      cin.tie(0); cout.tie(0);

      fill(&dp[0][0], &dp[0][0] + 1010 * 2, 1);

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

      //cout << "\n";
      int result = 1;
      for (int i = 1; i <= n; i++) {
            int nowNum = arr[i];
            //cout << "arr[i] : " << arr[i] << "\n";

            for (int j = i-1; j > 0; j--) {           //자신보다 이전에 나온 것들을 돈다.
                  //cout << "arr[j] : " << arr[j];
                  if (nowNum < arr[j]) {        //현재 숫자보다 큰 값을 만났다.
                        //일단 지금까지의 최대값인지 정해야한다.
                        //cout << "  in arr[i] < arr[j]\n";
                        dp[i][0] = max(dp[i][0], dp[j][1] + 1);
                        dp[i][0] = max(dp[i][0], dp[j][0] + 1);
                  }
                  else if (nowNum > arr[j]) {
                        //cout << "  in arr[i] > arr[j]\n";
                        dp[i][1] = max(dp[i][1], dp[j][1] + 1);
                  }
                  else {
                        //cout << "  Same\n";
                  }
            }

            //cout << "i : " << i;
            result = max({ result, dp[i][0], dp[i][1] });
            //cout << "  dp[i][0] : " << dp[i][0] << "  dp[i][1] : " << dp[i][1] << "\n\n";
       }

      //cout << "result : ";
      cout << result;
}

 

기본 아이디어는 dp에 현재 숫자가 제일 높을 때와 제일 낮을 때를 저장하는 것이다.

제일 낮을 때라는 가정은 2가지를 비교해야하는데 자신보다 큰 숫자가 왔을 때

해당 숫자가 가장 낮을 때 그 뒤에 오는 경우가 있고 (1234521) 큰 숫자 바로 뒤에 오는 경우(123452)가 있기에 2경우를 비교해야한다.