[boj : 15886] 내 선물을 받아줘2

www.acmicpc.net/problem/15886

15886번: 내 선물을 받아줘 2

문제 : 'E' 와 'W'가 주어지고 선물을 구사과님이 어느 칸에서부터 시작하더라도 먹을 수 있도록 배치해야된다. 이때 최소의 선물만 배치해야된다.

 

해설 : 'E'로 시작하면 'W'를 만나지 않을때까지 전진한다. 그리고 'W'를 만나면 다시 돌아간다. 이는 'E'의 끝에 선물을 하나 놓으면 이 위치를 기준으로 왼쪽으로는 'E' 오른쪽으로는 'W'는 무조건 선물을 먹게 된다는 뜻.

ex) EEEEEEEEEEEEEEEEEEEEEEEEEEEWWWWWWWWWWWWWWWWW

그럼 다 해결된거다. 새롭게 시작되는 E만 찾아서 개수를 세어주면 된다.

 

#include<bits/stdc++.h>

using namespace std;

int v[1000];
string s;

void dfs(int x);
int main()
{
	int n,ans=0;	

	cin >> n >> s;
	for (int i = 0; i < s.length(); i++)
		if (!v[i] && s[i] == 'E') {
			dfs(i);
			ans++;
		}
	cout << ans;
	return 0;
}
void dfs(int x)
{
	if (v[x])return;
	v[x] = 1;

	if (s[x] == 'E')dfs(x + 1);
	else dfs(x - 1);
}