[BOJ/백준 14659][C++] 한조서열정리하고옴ㅋㅋ

문제

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

 

문제 내용

아래와 같이 봉우리들에 활잡이들이 한 명씩 있다.
모든 활잡이는 자신의 오른쪽으로 활을 쏠 수 있으며, 자신보다 낮은 위치의 적만 잡을 수 있다.
최고의 활잡이가 처치할 수 있는 적의 최대 숫자를 출력하면 된다.

 

문제 풀이

반복문과 조건문을 통해 봉우리의 높이를 비교해야 한다.

위의 사진을 보면, 봉우리가 0번부터 시작한다고 했을 때, 2번과 3번 봉우리를 비교하면 2번이 더 높다.
그렇기 때문에 3번은 자신보다 낮은 봉우리의 개수가 몇 개인지를 구할 필요가 없다.

즉, 자신보다 낮은 봉우리의 개수를 카운트 하다가 자신보다 높은 봉우리를 만나면
지금까지 지나온 낮은 봉우리 개수와, 이전에 카운트했던 개수를 비교하여 max 값을 저장하면 된다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, a, mmax, cnt;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
    //입력
	cin >> n;
	vector<int>v;
	for (int i = 0; i < n; i++) {
		cin >> a;
		v.push_back(a);
	}
	
    //문제 해결
	a = 0, mmax = 0, cnt = 0;
	for (int i = 0; i < n; i++) {
		if (v[i] < a)
			cnt++; 	//낮은 봉우리 개수 카운트
		else {
			mmax = max(past_max, cnt);	//max값 저장하기
			cnt = 0;	//카운트 초기화
			a = v[i];	//봉우리 새로 설정
		}
	}
	mmax = max(past_max, cnt); //마지막에 한번 더 체크해줘야 한다.
	
    //결과 출력
    cout << past_max << '\n';
}

 

문제 코드 설명

1) 입력

봉우리 개수 N을 입력받아 배열을 생성할 것이기 때문에 vector를 사용한다.

 

2) 문제 해결

반복문과 조건문을 사용하여 봉우리의 높이를 비교하면 된다.