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

문제 링크 :

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=393&sw_prbl_sbms_sn=14661 

 

문제 개요 : 

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

 

#include<iostream>
#include<vector>
#include<algorithm>
#define INF 987654321 // 무한대 값 정의

using namespace std;

int main(int argc, char** argv)
{
  int N; // 돌의 개수를 저장할 변수
  int res; // 정답을 저장할 변수

  cin >> N; // 돌의 개수를 저장한다
  vector<int> map(N); // 돌의 높이를 저장할 벡터
  vector<int> cnt(N,0); // 각 돌마다 증가수열 + 감소수열 값을 저장할 벡터
  vector<int> database1(N,INF); // 앞에서부터 탐색 -> 최대 증가수열 저장할 벡터
  vector<int> database2(N,INF); // 뒤에서부터 탐색 -> 최대 감소수열 저장할 벡터
  int idx1=0, idx2=0; // 각 데이터베이스의 최대 인덱스

  for (int i=0;i<N;i++){
    scanf("%d", &map[i]); // 각 돌의 높이를 저장한다
  }
  int k = N;
  for (int i=0;i<N;i++){
    k--; // i는 앞에서부터 탐색, k는 뒤에서부터 탐색
    if (database1[0] >= map[i]) {database1[0] = map[i];} // 가장 낮은 돌은 0번째 인덱스에 저장
    else if (database1[idx1] < map[i]) { // 가장 높은 돌은
        cnt[i] += ++idx1; // idx1 만큼의 길이를 갖는 증가수열을 가진다
        database1[idx1] = map[i]; // 그리고 그 돌의 높이를 데이터베이스에 저장
    }
    else { // i번째 돌의 높이가 중간 어디쯤이라면 이분탐색으로 찾는다
      int low = 0; // 가장 작은 인덱스
      int high = idx1; // 가장 큰 인덱스
      int mid; // 이분탐색에서 쓸 평균 값
      while(true) {
        mid = (low + high) / 2; // 평균 값을 구하고
        if ((database1[mid-1] < map[i]) && (database1[mid] >= map[i])) { // 적절한 위치를 찾으면
          cnt[i] += mid; // 증가수열의 길이를 더해주고
          database1[mid] = map[i]; // 그 돌의 높이를 데이터베이스에 저장
          break;
        }
        else if (database1[mid-1] > map[i]) {high = mid - 1;} // 적절한 평균값을 찾기 위한 계산
        else {low = mid + 1;} // 적절한 평균값을 찾기 위한 계산
      }
    }

    // 이하는 위와 같은 과정인데, k 변수를 이용해 뒤에서부터 탐색한다
    if (database2[0] >= map[k]) {database2[0] = map[k];}
    else if (database2[idx2] < map[k]) {
        cnt[k] += ++idx2;
        database2[idx2] = map[k];
    }
    else{
      int low = 0;
      int high = idx2;
      int mid;
      while(true) {
        mid = (low + high) / 2;
        if ((database2[mid-1] < map[k]) && (database2[mid] >= map[k])) {
          cnt[k] += mid;
          database2[mid] = map[k];
          break;
        }
        else if (database2[mid-1] > map[k]) {high = mid - 1;}
        else {low = mid + 1;}
      }
    }
  }

  res = *max_element(cnt.cbegin(), cnt.cend()) + 1; // 증가+감소 수열의 최대 길이를 구한다
  printf("%d\n", res); // 결과를 출력한다

  return 0;
 }

 

주의해야 할 점

1. 증가하다가 감소하는 최대 길이의 수열을 찾는 문제이다.

2. 앞에서부터 증가수열의 길이를 계산하고 뒤에서부터 감소수열의 길이를 계산하면 된다.

3. 그런데 아무생각 없이 풀면 for문을 2번 돌리게 되어 O(N^2)으로 시간초과가 나온다.

4. 시간초과를 피하기 위해서 이분탐색을 이용해 O(NlogN)으로 시간을 줄인다.

5. 이분탐색을 하기위해 database라는 벡터를 만든다.

database의 값이 의미하는 것 : 돌의 높이

database의 인덱스가 의미하는 것 : 이 돌 앞에는 길이가 idx인 증가수열이 존재한다.

6. 반복문을 돌면서 다음과 같은 작업을 수행한다.

돌의 높이가 최솟값이라면 그 돌의 최대 증가수열의 길이는 0이다.

돌의 높이가 최댓값이라면 '현재 가장 긴 증가수열의 길이+1'이 그 돌의 최대 증가수열이다.

돌의 높이가 최대도 아니고 최소도 아니라면 database 이분탐색을 통해 그 돌의 최대 증가수열이 무엇인지 알아낼 수 있다.

7. 증가수열+감소수열의 최댓값을 출력하면 정답을 얻을 수 있다.