[usaco] 1.1 Broken Necklace - usaco
2009.08.08 19:30 Edit
/* ID: neoevok1 PROG: beads LANG: C++ */ #include <iostream> #include <fstream> #include <string>
using namespace std;
int n;
int travel(string a, int s, int d)
{
int backup_s=s;
int cnt=1;
char status=a[s];
while(1)
{
s+=d;
if(s>=n) s-=n;
if(s<0) s+=n;
if(backup_s==s) return cnt;
if(status!='w' && a[s]!='w' && a[s]!=status)
return cnt;
if(a[s]!='w')
status=a[s];
cnt++;
}
return -1;
}
int main() {
ofstream fout ("beads.out");
ifstream fin ("beads.in");
fin >> n;
string a;
fin >> a;
int m=travel(a,0,1)+travel(a,n-1,-1);
if(m>n) m=n;
for(int i=1;i<n;i++)
{
int cnt=travel(a,i,1);
if(cnt==n) {
m=cnt;
break;
}
cnt+=travel(a,i-1,-1);
m=max(m,cnt);
}
fout << m << endl;
return 0;
}
1.1 치고는 꽤 복잡한 문제이다.
흰색이 맨 처음에 있는 것과 어떤 색깔로 정해진 후에 흰색이 나타나는 것을 잘 고려하여 코딩하면 된다.


