백준] 14720 - 우유 축제(충남대학교 생각하는 프로그래밍 대회)

시간 제한 : 1초

메모리 제한 : 256MB

입력

첫째 줄에 우유 가게의 수 N이 주어진다. (1 ≤ N ≤ 1000)

둘째 줄에는 우유 가게 정보가 우유 거리의 시작부터 끝까지 순서대로 N개의 정수로 주어진다.

0은 딸기우유만을 파는 가게, 1은 초코우유만을 파는 가게, 2는 바나나우유만을 파는 가게를 뜻하며, 0, 1, 2 외의 정수는 주어지지 않는다.

출력

영학이가 마실 수 있는 우유의 최대 개수를 출력하시오.

소스코드

#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
	int n, cnt, state, start = -1;
	bool check = false;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
		if (arr[i] == 0 && !check)
			check = true, start = i;
	}
	
	if (!check)
		cout << 0;
	else {
		state = 0, cnt = 1;
		for (int i = start+1; i < n; i++)
		{
			int tmp = (state + 1) % 3;
			if (tmp == arr[i])
				state++, cnt++;
		}
		cout << cnt;
	}
}

Tip

처음에는 DP로 접근하려고 했으나, 문제에서 제시된 조건에 따르면 무조건 다음 우유가 정해져 있기 때문에, 0이 최초로 시작하는 지점에서부터 우유를 패턴에 맞춰 먹어가는 방향으로 문제를 풀었다.