[백준]36진수(1036)

문제 링크 : [백준]36진수(1036)

문제 설명

N개의 36진수가 주어졌을 떄, K개의 숫자를 Z(10진수로 35)로 바꾸었을 때 가능한 최대값을 출력하세요.

입력

N(수열의 갯수, 1 <= N <= 50)
V_i(36진수(최대 50자리))
K(변경할 수 있는 숫자의 갯수, 0 <= K <= 36)

5
GOOD
LUCK
AND
HAVE
FUN
7

출력

31YUB

카테고리

#정렬 #큰수 #그리디

시간 복잡도 상한

O(N!), O(K!) 만 아니면 될거 같아요??

해결 방법

1. 자리수가 50자리이고, 거기다 36진수이기 때문에 언어에서 제공하는 자료형으로는 어렵습니다.
2. 따라서 36진수 덧셈을 먼저 구현해야 합니다.
3. 큰 수는 문자열로 처리해야 하며, 입력받은 값을 거꾸로 뒤집어야 자리수를 맞추는 번거로움을 줄일 수 있습니다.
   3-1. 예시)ABC + ABCD 로 주어졌을 때, 그대로 연산하게 되면, 두 문자열의 자리수를 구하여, 첫번째 수의 맨 앞자리에 패딩을 넣어 자리수를 맞추어야 하지만, 두 수를 거꾸로 뒤집어, CBA + DCBA로 하면, 인덱스 보정없이 바로 계산이 가능합니다.
4. 거꾸로 저장을 하였다면, 각 인덱스마다 두 수를 더하면 됩니다.
5. 하지만 덧셈에는 자리 올림이 발생하니 그것도 처리를 해주면 됩니다.
6. 여기까지는 귀찮기는 하지만 어려운 것을 없을 것입니다.
7. 문제는 여기부터!! 36진수(0~Z)중 K개의 수를 Z로 바꾸는 모든 경우 중 최대값을 구해야 합니다.
8. 모든 주어진 수에서 나타난 각각의 수를 따로 저장합니다.
   8-1. 123 + 312 + 523 이라고 한다면,
   8-2. 1은 100 + 10 = 110
   8-3. 2는 20 + 2 + 20 = 42
   8-4. 3은 3 + 300 + 3 = 306
   8-5. 요렇게 저장합니다.
   8-6. 하지만 사실 나중을 위하여, 1을 예로 들면, Z00 - 100 + Z0 - 10 으로 계산합니다.
   8-7. 현재 숫자를 Z로 바꿨을 때 얻을 수 있는 이득을 계산합니다.
9. 각 숫자별로 그 수를 Z로 바꾸었을 때 얻을 수 있는 이득들이 모두 계산되었습니다.
10. 이 중 K개를 골라 최대값을 만들려면 이득이 최대로 되는 K개를 구하면 됩니다.
11. 즉 이득으로 내림차순으로 정렬하여, 6까지에서 구한 값에다가 K개의 수를 바꿈으로써 얻을 수 있는 이득을 더해줍니다.

시간복잡도

O(N)

코드

#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
int n,m,d[60],i,j,l;
struct E{
    int s[60];
    bool operator <(const E &a)const{
        for(int i=59;i>=0;i--){
            if(s[i]>a.s[i])return true;
            if(s[i]<a.s[i])return false;
        }
        return false;
    }
}e[36];
char s[51],t;
int main(){
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%s",s);
        l=strlen(s);
        for(j=0;j<l;j++){
            t=s[l-j-1];
            if(t<'A'){
                d[j]+=t-'0';
                e[t-'0'].s[j]+=('9'-t+26);
            }else{
                d[j]+=t-'A'+10;
                e[t-'A'+10].s[j]+=('Z'-t);
            }
        }
    }
    scanf("%d",&m);
    for(i=0;i<59;i++){
        d[i+1]+=d[i]/36;
        d[i]%=36;
        for(j=0;j<36;j++){
            e[j].s[i+1]+=e[j].s[i]/36;
            e[j].s[i]%=36;
        }
    }
    sort(e,e+36);
    for(l=i=0;i<59;i++){
        for(j=0;j<m;j++)d[i]+=e[j].s[i];
        d[i+1]+=d[i]/36;
        d[i]%=36;
        if(d[i])l=i;
    }
    for(;l>=0;l--)printf("%c",d[l]>9?d[l]-10+'A':'0'+d[l]);
}