[백준OJ] 16162번 가희와 3단 고음

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

16162번: 가희와 3단 고음

---

 

-풀이-

처음엔 문제가 이해되지않아서 곰곰히 문제를 다시보니, 등차수열의 최대 개수를 찾아야되는 문제이다.

등차수열이란 An=A0+d(n-1) 을 만족하는 식이된다.

 

이문제를 풀기위해 나는 stack자료형을 사용하여 배열을 한번 쭉 탐색했다. 탐색하면서.

1) 먼저 스택이 비어있을땐, 처음항인 a가 들어와야 한다.

2) 스택이 비어있지 않을때는, 스택의 top부분이 연속되는 등차수열의 마지막항이 되므로, 스택의 TOP에있는 원소+d가 있다면, push를 한다.

 

이렇게 등차수열의 최대 개수(스택의 사이즈) 를 출력하면된다.

 

-시간복잡도-

배열을 한번 탐색하면 되므로 O(N)이 걸린다.

 

-코드-

 

#include<iostream>
#include<algorithm>
#include<stack>

using namespace std;

int arr[20001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, a, d;
	int answer = 0;
	stack<int> st;
	cin >> n >> a >> d;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	for (int i = 0; i < n; i++) {
		int now = arr[i];
		if (now==a&&st.empty()) {
			st.push(now);
		}
		else {
			if (!st.empty()&&st.top() + d == now) {
				st.push(now);
			}
		}
	}
	cout << st.size() << "\n";

	return 0;
}