[백준 27972번] 악보는 거들 뿐 (C++)

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

27972번: 악보는 거들 뿐

와쿠컵에 출제되었던 문제다. 풀타임으로 하고 싶었지만 교수님께서 중간고사를 2번본다는 말씀을 하셔서 짝수번만 풀다가 음악을 좋아해서 문제 제목보고 풀려다가 한번에 못푼 문제였다.

틀린 문제들 다시 풀다가 이번에 풀었는데, 생각보다 너무 바로 아이디어가 떠올라서 허무했다.

왜 그때 한번에 떠올리지 못했을까...하이튼 그리디문제이고 별로 어려운 문제도 아니라고 생각한다.

 

풀이는 악보 수열을 받아서 연속적으로 증가 또는 감소하는 부분이 가장 큰 것을 찾으면 된다.예를 들어 10 8 4 6 7 8 1 2 3 이 있다면, 가장 긴 부분은 4 6 7 8이 될 것이다. 따라서 최소인 N = 4가 된다.코드는 다음과 같다.

 

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

using namespace std;
int main(){
  int n, up = 0, down = 0, ans = 0;
  cin >> n;
  int *sheet = new int[n];
  for(int i = 0; i < n; i++){
    cin >> sheet[i];
  }

  for(int i = 1; i < n; i++){
    if(sheet[i] > sheet[i-1]){
      down = 0; up++;
      ans = max(ans,up);
    }else if(sheet[i] < sheet[i-1]){
      down++;
      up = 0;
      ans = max(ans,down);
    }
  }
  cout << ans+1;
}

 

 

 

 

대회때는 익숙한 파이썬으로 풀려고 했고, 요즘 C++로 연습중이다.