백준 12970 AB

문제 URL : https://www.acmicpc.net/problem/12970

 

문제 접근법 : 

처음엔 전수조사해서 풀려고 했으나 2^50 이라 가능할것같지 않아서

수학적으로 접근했습니다.

 

만약 ABBBBABB 가 있따면

뒤에 있는B뒤에있는 B들은 전부 A의 개수만큼 더해줘야하기때문에

01111022 가 되는 구조라

처음부터 n의 길이만큼 B로 설정해줍니다.

그럼 어딘가 k개 이하만큼 A를 잘 설정해줘야하는데

n이 6이라고 가정하고 k에 상관없이

처음 BBBBBB 로시작해

0번째에 A를 놓는다고가정하면

ABBBBB 가 되고 011111 만큼 count하면 5가 되고

중간 아무 위치에 A를 넣을때 어떻게 카운트하냐면

ABABBB일때 010222가 된다면 7이 되는데 A의 인덱스위치에서 n-1-i 만큼 카운트해주고 또 앞에 a가 붙여줌으로서 기존껄 지워줘야하니 a의 개수만큼 지워주면 되기때문에

전체 합이 k이하가 될수있는지만 판단해서 a를 놓으면 되는 알고리즘으로 짰습니다.

 

소스코드:

//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
int n,k;
void input(){
    cin>>n>>k;
}

void solve(){
    string res ="-1";
    string s(n,'B');
    int total = 0;
    int cnt = 0;
    for(int i=0;i<n;i++){
        if(total -1 +n-i-cnt<=k){
            s[i]='A';
            total+=n-i-1-cnt;
            cnt++;
        }
        if(total==k){
            res=s;
            break;
        }
    }
    cout<<res<<"\n";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    input();
    solve();

}

 

궁금한점 혹은 모르는점 혹은 논리적인 오류등 어떤질문이든 댓글은 언제나 환영입니다.