뚝딱뚝딱

https://softeer.ai/practice/6293

💡 징검다리

• 징검다리 문제는 입력이 3*1000까지 이기 때문에 n^2으로 풀이할 수 있다.
• 계수 정렬을 이용하여 풀이한다.
• 각 돌의 계수를 저장하기 위한 크기가 N인 vector를 생성하고, 값을 1로 초기화해준다.
• 1로 초기화 해주는 이유는, 어떠한 돌을 밟더라도 하나의 돌은 밟은 것이므로 1로 시작한다.
• 0번째를 제외하고, 1번째 돌부터 N-1번째 돌까지 순회하면서, 현재 돌이 이전 돌 보다 큰지를 확인한다.
• 0번째 돌부터 현재 돌의 이전 돌까지 중, 현재 돌보다 작은지 확인하고, 작은 돌들 중에서도 가장 큰 계수를 가져오고, 그 값에 1을 더하여 현재 돌의 계수를 설정하는 방식이다.
• 이런식으로 모든 돌의 계수를 설정하고 나서, 가장 큰 계수를 반환하면 그것이 답이 된다.

• 원리
  예시1
  
  

• n=5일때 위와 같이 돌의 높이가 주어졌다고 하자.
• 3은 시작이고, 이전 돌이 없으며 첫 돌이므로 본인을 포함한 1의 값을 갖는다.
• 2를 보면, 앞의 돌인 3보다 작기 때문에, 본인을 포함한 1의 값을 갖는다.
• 1역시, 앞의 돌인 3,2보다 작기 때문에, 본인을 포함한 1의 값을 갖는다.
• 4는 앞의 돌인 3,2,1보다 크고, 이 중 가장 큰 계수 값이 1이므로, 1에 본인을 포함한 1을 더해 2의 값을 갖는다.
• 5는 앞의 돌인 3,2,1,4보다 크고, 이 중 가장 큰 계수 값이 2이므로, 2에 본인을 포함한 1을 더해 3의 값을 갖는다.
• 따라서 최종적으로 가장 큰 계수인 3이 최대로 건널 수 있는 돌의 개수와 같다.

• 예시2
  
  

• • n=7일때 위와 같이 돌의 높이가 주어졌다고 하자.
  • 1까지 앞의 내용과 같다.
  • 6는 앞의 돌인 3,2,1보다 크고, 이 중 가장 큰 계수 값이 1이므로, 1에 본인을 포함한 1을 더해 2의 값을 갖는다.
  • 7은 앞의 돌인 3,2,1,6보다 크고, 이 중 가장 큰 계수 값이 2이므로, 2에 본인을 포함한 1을 더해 3의 값을 갖는다.
  • 4는 앞의 돌인 3,2,1보다 크고, 이 중 가장 큰 계수 값이 1이므로, 1에 본인을 포함한 1을 더해 2의 값을 갖는다.
  • 5는 앞의 돌인 3,2,1,4 보다 크고, 이 중 가장 큰 계수 값이 2 이므로, 2에 본인을 포함한 1을 더해 3의 값을 갖는다.
  • 따라서 최종적으로 가장 큰 계수인 3이 최대로 건널 수 있는 돌의 개수와 같다.

이런식으로 동작하는 것이고, 2줄 for문을 거치기 때문에 n^2의 시간 복잡도가 발생한다.

전체 코드는 아래와 같다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(int argc, char** argv)
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int N;
  cin>>N;

  vector<int> h(N);//높이를 담을 벡터
  for(int i=0; i<N; i++){
    cin >> h[i];
  }
  
  vector<int> cnt(N,1);//계수를 담을 벡터
  for(int i=1; i<N; i++){
    int cnt_max=0;//이전 계수 중, 돌의 높이가 현재 돌보다 작으면서, 계수가 가장 큰 것을 저장하기 위함
    
    for(int j=0; j<i; j++){
      if(h[i]>h[j]){//이전 돌이 현재 돌보다 작으면
        cnt_max = max(cnt_max, cnt[j]);
      }
    }

    cnt[i]=cnt_max+1;//이전 계수에 현재 돌까지 합쳐서 계수 설정
  }

  cout<<*max_element(cnt.begin(), cnt.end());

   return 0;
}

***참고로 vector의 max값을 반환하기 위해 vector에서 제공하는 max_element() 메서드를 사용했는데, 이 함수는 iterator 즉, 벡터의 요소를 가리키기 때문에, 그 값을 가져오려면 앞에 *를 붙여야 한다.