[usaco] 1.1 Broken Necklace - usaco

 /*
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 치고는 꽤 복잡한 문제이다.

흰색이 맨 처음에 있는 것과 어떤 색깔로 정해진 후에 흰색이 나타나는 것을 잘 고려하여 코딩하면 된다.


Leave Comments


profileneoevoke난 전설 같은건 믿지 않아 

Category

Recent Post

Recent Trackback


T-NAVI