글 읽기 - 6%에서 삑사리가 납니다.

chayhyeon 1년 전 0

질문에 있는 모든 테스트 케이스도 통과했고, 이 코드를 파이썬으로도 고쳐서 제출해봤지만 6%에서 틀렸습니다가 계속 뜨네요..

제 코드는 각 문자별로 Z로 바꿨을 때 얼마나 이득을 보는지 계산한 다음,

그 이득이 큰 순서대로 k번을 바꾸어 준 뒤에

마지막에 바뀐 수들을 전부 합해줍니다.

혹시 어느 케이스에서 반례가 생기는지 고수님들의 도움이 필요합니다..!

#include <cstdio>
#include <cctype>

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int n, k;
vector<string> v;
string greedy[36]; // 각 문자를 Z로 바꾸면 생기는 이득


bool compare(const string &a, const string &b){
    if(a.length() > b.length()) return true;
    if(a.length() == b.length() && a > b) return true;
    else return false;
}


int to_dec(char a){ // 36진수를 10진수로
    return isalpha(a) ? a - 'A' + 10 : a - '0';
}


char to_36(int a){ // 10진수를 36진수 알파벳으로
    return a >= 10 ? 'A' + (a-10) : a + '0';
}


string sum_36(string a, string b){
    if(a.length() < b.length()){ // a가 크게
        string c = a;
        a = b;
        b = c;
    }
    int s = a.length() - b.length();
    int len = b.length();
    int next = 0;
    for(int i=len-1; i >= 0; i--){
        int x = to_dec(a[i+s]);
        int y = to_dec(b[i]);
        int z = x + y + next;
        if(z >= 36){ // 자리올림
            next = 1;
            z -= 36;
        }
        else next = 0;
        a[i+s] = to_36(z);
    }
    if(next){
        while(s > 0 && (a[s-1] == 'Z')){
            a[s-1] = '0';
            s--;
        }
        if(s == 0) a.insert(0, "1");
        else a[s-1] = to_36(to_dec(a[s-1])+1);
    }
    return a;
}


string z_tf(string a, char b){
    for(int i=0; i<a.length(); i++)
        if(a[i] == b) a[i] = 'Z';
    return a;
}


void calc_benefit(){
    for(int i=0; i<n; i++){
        int len = v[i].length();
        for(int j=len-1; j>=0; j--){
            string temp("");
            temp += to_36(to_dec('Z') - to_dec(v[i][j]));
            for(int k=0; k<len-1-j; k++)
                temp += "0";
            greedy[to_dec(v[i][j])] = sum_36(greedy[to_dec(v[i][j])], temp);
        }
    }
}


char get_max_benefit_char(){
    char ret='0';
    string max_benefit("0");
    for(int i=0; i<36; i++)
        if(compare(greedy[i], max_benefit)){
            max_benefit = greedy[i];
            ret = to_36(i);
        }
    return ret;
}


int main(){
    scanf("%d", &n);
    string input;
    for(int i=0; i<n; i++){
        cin >> input;
        v.push_back(input);
    }
    scanf("%d", &k);
    // init greedy
    for(int i=0; i<36; i++)
        greedy[i] = "0";
        
    calc_benefit();
    
    for(int i=0; i<k; i++){
        char to_change = get_max_benefit_char();
        greedy[to_dec(to_change)] = "0";
        for(int j=0; j<n; j++)
            v[j] = z_tf(v[j], to_change);
    }
    
    
    string ans(v[0]);
    for(int i=1; i<n; i++){
        ans = sum_36(ans, v[i]);
    }
    
    cout << ans;
}

semi0777 1년 전 0

코드를 알아보기 어렵네요 get을 이용해서 char형식으로 받아온 다음 sort를 사용해서 정렬 후 예제를 풀어보시는건 어떨까요

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

문제

문제

출처

ICPC

6%에서 삑사리가 납니다.

chayhyeon 1년 전 0

semi0777 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말