백준 1965 C++

문제

풀이

문제를 간단히 설명하면 띄엄띄엄 있더라도 숫자가 점점 증가하는 수열의 길이를 구하는 것이다. 이런 문제가 다들 그러하듯이 DP문제이다. Arr배열과 DP배열을 둘 다 사용했다.

문제를 풀이하면 나오는 것은 자신 이전의 원소에서 작은 원소들을 찾는다. 그리고 그 작은 원소들 중에서 dp에 들어가 있는 값 + 1이 자신의 dp값보다 크면 그 값으로 자신을 바꾼다.

즉, 상자안에 들어갈 수 있는 이전 상자들의 최댓값을 끝까지 갱신하는 방식의 풀이다.

기본으로 주는 예제로 보면(1, 5, 2, 3, 7)이다. 거기서 일단 상자는 자기 자신이 있으니 최소 1개이니. dp에 각각 1개씩은 있다고 해줘야한다. 배열을 하나하나 1,5,2,3,7 순서대로 설명하면

첫 번째 1같은 경우에는 자기 자신이외에 볼 것이 없으니 dp[1] = 1로 끝난다.

두 번째 5의 이전의 원소는 1이다. 1은 5보다 작다. 1의 dp + 1은 2이고, 5의 dp는 1이니 5의 dp, 즉 dp[2]는 2로 갱신이 된다.

세 번째 2보다 이전의 수중에 작은 숫자는 첫 번째의 1이 있다. 1의 dp는 1이고, 현재 세 번째 2의 dp는 1이다. 그러니 조건에 맞춰 갱신해야하니 2의 dp에 1+1이 들어가 2가 된다. dp[3]는 2로 갱신된다.

네 번째 3은 이전에 작은 수는 첫 번쨰 1과 세 번째 2가 있다. 1의 dp는 1이고, 2의 dp는 2이다. 여기서 가장 큰 것을 택해 + 1 한 것을 더하는 식이니 dp[4]는 3으로 갱신된다.

마지막 7은 이전에 작은 수는 1,5,2,3이 있다. 1의 dp는 1, 5의 dp는 2, 2의 dp는 2, 3의 dp는 3이다. 여기서 가장 큰 것은 3의 dp값은 3이니 dp[4] = 3 + 1을 해주는 식이 되어 dp갱신은 끝이난다.

그리고 마지막으로 dp값들을 쭉 돌며 가장 큰 값을 찾으면 된다.

이런 식으로 코드를 짜면 아래의 코드가 나온다.

코드

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


int N;
int arr[1001];
int dp[1001];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  cin >> N;
  for (int x = 1; x <= N; x++) {
    cin >> arr[x];
  }
  
  int ans = 0;
  for (int x = 1; x <= N; x++) {
    dp[x] = 1;
    for (int y = 1; y <= N; y++) {
      if (arr[y] < arr[x] && dp[x] < dp[y] + 1)
        dp[x] = dp[y] + 1;
    }
    ans = max(ans, dp[x]);
  }
  cout << ans;
  return 0;
}

BOJ 카테고리 내 다른 글 보러가기