[백준] 30804번 과일 탕후루 C++ 풀이

---

알고리즘 분류

• 구현
• 브루트포스 알고리즘
• 투포인터

---

문제 설명

---

입력 설명

---

출력 설명

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

---

예제 입력

5
5 1 1 2 1

3
1 1 1

9
1 2 3 4 5 6 7 8 9

---

예제 출력

4

3

2

---

아이디어

과일을 하나씩 꽂다가 서로 다른 종류의 과일이 2개를 초과하면 서로 다른 종류의 과일이 2개 이하가 될 때까지 맨 처음 끼운 과일부터 뺀다.

이때의 과일의 개수를 저장하여 저장된 과일의 개수 중 가장 큰 값을 출력한다.

---

알고리즘

과일을 입력받을 때마다 과일 수를 증가시키고 기존에 입력받은 적 없는 과일이라면 과일 종류도 증가시킨다.

과일 종류가 2가지를 초과하면 2이하가 될 때까지 list의 front에서 pop 한다.

그리고 과일 종류가 2 이하가 되면 이때의 남은 과일의 수를 기록하여 최댓값을 출력한다.

---

코드

#include <iostream>
#include <list>
using namespace std;
int main()
{
	int N,max=0,type=0;
	cin>>N;
	list<int> li;
	int arr[10]= {0};
	while(N--)
	{
		int n, cnt=li.size();
		cin>>n;
		if(arr[n]++ == 0) type++;
		li.push_back(n);
		cnt++;
		while(type>2)
		{
			if(--arr[li.front()] == 0) type--;
			li.pop_front();
			cnt--;
		}
		if(max < cnt) max = cnt;
	}
	cout<<max;
	return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/30804

처음에는 앞에서 빼는 것과 뒤에서 빼는 것을 모두 다 해보며 기록하는 DP를 생각했지만

투포인트가 더 좋을 것 같아서 투포인트로 해결했다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!