글 읽기 - 반례를 찾을 수 있을까요?

yuiyui128 5년 전 0

나름 규칙을 찾아 재귀로 풀었습니다.

( 입력받은 문자열의 길이에서 만들 수 있는 순서쌍의 최대값을 구한 뒤 문자열을 만든다)

어떤 반례가 있을까요??

틀린 경우를 찾기 위해 제가 출력한 알파벳으로 순서쌍을 찾는 코딩을 추가로 해봤지만 제가 해본 결과 안에서는 다 정답으로 뜨네요 .. ㅠㅠ 고수님들의 답변 기다리겠습니다.

#include <iostream>
#include <vector>

using namespace std;

int N, K;
vector<int> v;

bool rf(int s, int f, int cnt, int alpha){ // start, finish, count, what_alphabet
    if(K == (f-s-(cnt)) * (cnt)){ // 제일 끝 바꿨을 때 딱맞으면
        v[f-cnt] = alpha;
        return true;
    }
    else if ( K < (f-s-cnt) * cnt){ // 제일 끝 바꾼거보다 작으면
        v[s+ K - (f-s-(cnt-1)) * (cnt-1) + (cnt-1)] = alpha;
        return true;
    }
    else { // 제일 끝 바꾼거 보다 크면
        v[f-cnt] = alpha;
        if(cnt >= (f - s + 1)/2){ // 절반 이상으로 바꿨으면
            if(alpha == 2) return false;
            K -= (f-s-cnt) * cnt;
            return rf(f-cnt, f, 1, alpha+1);
        }
        return rf(s, f, cnt+1, alpha);
    }
    return false;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> K;
    v.clear();
    v.resize(N);
    
    if(rf(0,N,1,1)){
        for(int i = 0 ; i < N; i++){
            switch(v[i]){
                case 0:
                    cout << "A";
                    break;
                case 1:
                    cout << "B";
                    break;
                case 2:
                    cout << "C";
                    break;
            }
        }cout << "\n";
    }else {
        cout << -1 << "\n";
    };
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 찾을 수 있을까요?

yuiyui128 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말