글 읽기 - 반례좀 제발 알려주세요

seonh4996 3년 전 0

제발 제발 반례좀 알려주세요..

그리디 형식으로 풀었습니다.

#include <bits/stdc++.h>

using namespace std;

vector<pair<vector<int>,char>> v;
vector<int> m(10,0);
bool check[10];
int N;
string str[51];
int main(){
    cin.tie(0);
    ios_base :: sync_with_stdio(0);
    for(int i = 0; i < 10; i++){
        v.push_back({vector<int>(14,0), 'A'+i});
    }
    cin >> N;

    for(int i = 0; i < N; i++){
        cin >> str[i];
        int sz = str[i].size();
        for(int j = 0; j < str[i].size(); j++){
            v[str[i][j] - 'A'].first[14-sz+j]++;
        }
        check[str[i][0] - 'A'] = true;
    }

    
    sort(v.begin(), v.end());
    
    for(int i = 0; i < 10; i++){
        if(check[v[i].second-'A'] == false){
            
            int j = i;
            while(j > 0 && v[j].first == v[j-1].first){
                swap(v[j-1],v[j]);
                j--;
            }
            swap(v[j], v[0]);
            sort(v.begin()+1, v.end());   
            break;
        }
    }
    
    for(int i = 0; i < 10; i++){
        int here = v[i].second - 'A';
        m[here] = i;
    }
    
    long long answer = 0;
    for(int i = 0; i < N; i++){
        long long n = 0;
        for(int j = 0; j < str[i].size(); j++){
            n += m[str[i][j]-'A'];
            n *= 10;
        }
        answer += n/10;
    }
    cout << answer;
}

p_ce1052 3년 전 1

방금 풀고오는 길인데 greedy로 풀 때는 0을 부여할 때 주의해야 하네요 가장 앞에 있는 자릿수 알파벳에 0이 부여되는 경우가 없도록이요. 저는 이거때문에 몇 번 틀렸는데 이미 고려하셨다면 도움이 못 돼드려 죄송합니다.

yj10516 3년 전 1

아 답은 1044고 올려주신 코드는 1040이 나옵니다.

seonh4996 3년 전 1

어우 감사합니다 ㅜㅜ

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

문제

문제

출처

ICPC

반례좀 제발 알려주세요

seonh4996 3년 전 0

p_ce1052 3년 전 1

yj10516 3년 전 1

yj10516 3년 전 1

seonh4996 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말