[백준 / BOJ] C++ 27972 악보는 거들 뿐

27972번: 악보는 거들 뿐

 

문제

https://www.acmicpc.net/problem/27972

27972번: 악보는 거들 뿐

 

 

풀이

음의 높낮이가 변하면 수를 1씩 늘리고 줄이기만 하므로 가장 긴 연속된 증가/감소하는 부분 수열의 길이가 정답이 된다. 연속이 끊길 때 길이 초기화를 1로 해야 함에 주의하자.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int m, a = 1, b = 1, ans = 0;
  cin >> m;
  vector<int> v(m, 0);
  for (int i = 0; i < m; i++) {
    cin >> v[i];
    if (i == 0)
      continue;
    if (a == 1 && b == 1) {
      if (v[i] > v[i - 1]) {
        a++;
      } else if (v[i] < v[i - 1]) {
        b++;
      }
    } else if (a > 1) {
      if (v[i] > v[i - 1]) {
        a++;
      } else if (v[i] < v[i - 1]) {
        b++;
        ans = max(ans, a);
        a = 1;
      }
    } else {
      if (v[i] > v[i - 1]) {
        a++;
        ans = max(ans, b);
        b = 1;
      } else if (v[i] < v[i - 1]) {
        b++;
      }
    }
  }
  ans = max(ans, max(a, b));
  cout << ans;
  return 0;
}