Softeer-연습문제-징검다리(C++)

문제 링크 :

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=390

 

문제 개요 : 

밟을 수 있는 돌의 최대 개수 구하기

 

#include<iostream>
#include<vector>

using namespace std;

int main(int argc, char** argv)
{
  int N, res=0;
  cin >> N;
  vector<int> map(N); // 돌의 높이 저장
  vector<int> cnt(N,1); // 현재까지 돌을 밟은 횟수
  for (int i=0;i<N;i++){
    cin >> map[i];
    int tmp=0;
    for (int j=0;j<i;j++){
      if (map[i]>map[j] && tmp<cnt[j]) tmp=cnt[j];
    } // 앞에 있는 돌 중에 cnt가 최대인 것을 알아낸다.
    cnt[i]=++tmp; // 그 값을 현재까지 돌을 밟은 횟수에 저장
    if (cnt[i]>res) res=cnt[i]; // 돌을 밟은 횟수의 최대값 저장
  }

  cout << res;

  return 0;
}

 

주의해야 할 점

현재 돌이 앞의 돌보다 높은지는 당연히 확인해줄 것이라고 생각한다. 그런데, 이것만 확인하면 답을 구할 수 없다. 현재 돌보다 낮은 돌들 중 cnt의 최댓값을 가지고 있는 녀석을 고르는 조건문을 작성해야 한다.

if (map[i]>map[j] && tmp<cnt[j])