[백준] 16438 원숭이 스포츠

 

기업 코딩테스트에서 떨어지면 아마 마음아픈 구현력 때문에 떨어지지 않을까 싶다..

 

이 문제는 원숭이들이 한번씩은 무조건 같은팀이 안되도록 7일간의 팀을 출력하면 된다!

왜 7 일인지를 생각해보면 2^7 = 128 이고 n<=99 이므로

반씩 계속 잘라가면서 팀을 시켜주면 무조건 가능하다!

그래서 l~r까지 반은 A 반은 B를 계속 해주면 된다 l>=r 까지!!

이걸 구현을 계속 틀렸다 굿... 싸늘하다.... 극망의 기운이 날아와 가슴에 꽂힌다..

구현은 잘하자..!!

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
 
char ans[7][111];
int n,cnt;
 
void solve(int l,int r,int dep){
    if(l >= r || dep==7) return;
    cnt=max(cnt,dep);
    int mid = (l+r)/2;
    for(int i=l;i<=r;i++){
        if(i<=mid) ans[dep][i]='A';
        else ans[dep][i]='B';
    }
    solve(l,mid,dep+1);
    solve(mid+1,r,dep+1);
}
 
int main(){
    //freopen("input.txt","r",stdin);
    scanf(" %d",&n);
    solve(1,n,0);
    for(int i=0;i<=cnt;i++){
        for(int j=1;j<=n;j++){
            if(ans[i][j]=='\0') ans[i][j] = (j%2==0) ? 'A' : 'B';
            printf("%c",ans[i][j]);
        } puts("");
    }
    while(cnt != 6){
        for(int i=0;i<n;i++){
            if(i&1) printf("A");
            else printf("B");
        } puts(""); cnt++;
    }
}