[SOFTEER] 징검다리

문제출처

• 징검다리

문제설명

• 남북으로 흐르는 개울에 동서로 징검다리가 놓여 있다.
• 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다.
• 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟으면서 개울을 지나려고 한다.
• 돌의 높이가 서쪽부터 동쪽 방향으로 주어졌을 때 철수가 밟을 수 있는 돌의 최대 개수를 구하라

문제접근

• 문제 설명이 아쉬운 면이 있지만, 제대로 이해를 해보자면 돌과 돌 사이의 간격은 중요하지 않다. 즉, 3000 개의 돌 중 어느 하나만 밟아도 건널 수 있다.
• DP 로 접근하여 풀면 vector<int> dp(N,1) 배열은 해당 인덱스에 해당하는 돌의 위치로 오기까지 최대로 밟을 수 있는 돌의 개수를 의미한다. 최소 한번씩은 밟을 수 있으므로 기본값은 1로 설정한다.
• dp 값은 이전 dp 값들 중 본인보다 높이가 낮은 돌들 중에서 최댓값 + 1 로 갱신한다.
• dp 배열에 저장된 값중 최댓값이 답이 된다.

구현

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

int main()
{
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  int N;
  scanf("%d", &N);
  vector<int> stones(N,0);
  for(int i=0; i<N; i++){
    scanf("%d", &stones[i]);
  }
  vector<int> dp(N, 1);
  for(int i=1; i < N; i++){
    int tmp = 0;
    for(int j=0; j<i; j++){
      if(stones[i] > stones[j])
        tmp = max(tmp, dp[j]);
    }
    dp[i] = tmp + 1;
  }
  int ans = *max_element(dp.begin(), dp.end());
  printf("%d\n", ans);
  return 0;
}