백준 30804 C++

백준 30804

문제

입력

출력

문제의 방법대로 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 첫째 줄에 출력하세요.

풀이

중요한 부분은 ‘과일의 각 종류에는 1부터 9까지의 번호가 붙어있고’, ‘과일을 두 종류 이하로 사용’ 이라는 말입니다.

그리고 조건은 ‘과일을 두 종류 이하로 사용한 탕후루 중에서 과일의 개수가 가장 많은 탕후루의 과일 개수’를 구하라. 입니다. 여기서 전형적인 투포인터 문제라고 판단할 수 있습니다. 또한 과일의 개수를 점점 늘려간다는 점에서 s = 0, e = 0으로 출발한다는 걸 알 수 있습니다.

e를 점점 늘려가면서, 과일 종류의 개수 카운트 배열의 값이 1일때 type을 ++해주고. 만약 그러다가 type이 3이상이 될 경우에 s를 앞으로 땡겨주면서, 과일의 종류를 줄여줍니다. 그러다가 다시 2개 이하가 되면 e를 늘려주는 일 반복…

그 모든 루프에서 max가 되는 과일의 개수를 카운팅해주면 되는 그리 어렵지 않은 투포인터 문제입니다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;
int N;
vector<int> v1;

int arr[10];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	v1.resize(N);

	int num = 0;
	for (int y = 0; y < N; ++y) {
		cin >> v1[y];
	}

	int s = 0, e = 0;
	int type = 0;
	int ans = 0;
	bool flag = false;
	while (e < N) {
		arr[v1[e]]++;//평소엔 앞으로 계속 가다가. 
		if (arr[v1[e]] == 1) type++;

		while (type > 2) {//type이 2개 초과하면 
			arr[v1[s]]--;//앞에 있는 것들 삭제. 
			if (arr[v1[s]] == 0) type--;
			s++;
		}

		ans = max(ans, e - s + 1);
		e++;
	}
	cout << ans;
	return 0;
}

BOJ 카테고리 내 다른 글 보러가기