백준 1036, 36진수

개요

문제 링크
골드 1, Greedy
K개의 수를 Z로 전환해 만든 N개의 36진수의 합의 최댓값 구하기

---

접근

1. 1339 와 매우 유사해 접근은 쉽게 할 수 있었다. 그런데 1339와 같은 방식으로 풀면 안된다. 1339의 방식은 자리수마다 count를 저장하고 큰 자리수의 count가 큰 문자에 대해 Z를 할당하는 것이다. 그런데 이렇게 풀면 주어진 예시부터 풀리지 않는다.

2. 왜그럴까? 우선 1339번은 입력되는 수의 개수가 최대 10개이다. 그 말은 각자리수의 합이 carry를 한 자리를 초과해 넘겨줄 수 없다는 말이다. 9×10+1 = 91 -> 9가 최대 carry가 될 것이다.

3. 그런데 이 문제는 입력이 50개가 들어와버린다. 만약 1의 자리에 Z가 50개가 들어와버리면 35×50 > 36×36이 된다. 2자리 위까지 carry가 영향을 줄 수 있게 된다.

4. 다음으로 p자리의 count가 같고, p-1자리의 count가 적다면 count가 적은 수를 Z로 만드는 것이 이득일 수 있다. 무슨 소린가 하니,

   // n=2, k=1
   1Y0
   Y00
   
   // 1->Z
   35*36^2 + 34*36
   34*36^2
   => [69,34,0]
   
   // Y-> Z
   1*36^2 + 35*36
   35*36^2
   => [36,35,0]

   Y의 count가 많지만 1을 바꾸는 것이 이득이 된다. 왜냐? 증명까지는 못하겠다. 그냥 우리는 저 상황을 이용하기만 하면 된다.

5. 그럼 어떻게 이용할 것이냐? 어차피 N×N=2500밖에 안되니까 O(N^4)을 돌려버려도 된다. 그러면 어떤 두 문자를 비교할 때, 단순히 count만 비교하는 것이 아니라 실제로 각각을 Z로 바꿔버린 뒤에 대소를 비교하면 되지 않을까?

6. 그래서 C++의 미친 장점. operator를 잘 이용하면 어렵지 않게 해결할 수 있다. 어떤 두 문자 A,B의 선호도를 비교할 때, A + B(Z)와 B + A(Z)의 대소를 비교해주면 된다. 어디서부터? 큰 자리수 부터.

   여기까지 다 짜놓고 WA가 여러번 났는데, vector의 operator를 설정할 때는 이미 만들어져 있는 "<"나 ">"를 사용하면 안됐다. 그래서 "-"로 바꿔주니 AC가 떴다.

---

Pseudo code

vector a - vector b {
    for (N~0)
        if (a[i] != b[i])
            return a[i] > b[i]
}

compare (A,B) {
    // 두번째 문제 해결
    // A를 Z로 바꿀 때 합이 크면 A가 우선
    // 합은 BigINT 써줘야 함
    return B+A.toz() - A+B.toz()
}

// length 자리수에 x가 1회 들어옴
for (x = string)
    count[x][length]++

// 첫번째 문제 해결, carry를 올려준다
for (count[A])
    carry_up()
sort(A, compare)

vector answer
for (i = N)
    for (j = A)
        answer[i] += count[j][i]*value[j]
carry_up(answer)

---

Source code

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

#define N 60
#define A 36
typedef vector <int> vec;

bool operator - (vec a, vec b) {
    for (int i=N; i>=0; i--)
        if (a[i]!=b[i])
            return a[i]>b[i];
    return 0;
}
int toi(char c) {
    return ('0'<=c&&c<='9')?c-'0':c-'A'+10;
}
char toc(int v) {
    return (0<=v&&v<=9)?v+'0':v+'A'-10;
}

struct node {
    bool t;
    int c[N+1], v;
    vec operator + (node b) {
        vec d(N+1,0);
        for (int i=0; i<N; i++) {
            d[i] += (c[i]*v+b.c[i]*35);
            d[i+1] += d[i]/A;
            d[i] %= A;
        }
        return d;
    }
    bool operator < (node b){
        if (!t && b.t) return 0;
        if (t && !b.t) return 1;
        node a = *this;
        return (b+a) - (a+b);
    }
    void set() {
        for (int i=0; i<N; i++) {
            c[i+1] += c[i]/A;
            c[i] %= A;
        }
    }
};

node a[A];
int main() {
    int n, m, k;
    cin >> n;
    string s;

    for (int i=0; i<n; i++) {
        cin >> s;
        m = s.size();
        for (int j=0; j<m; j++) {
            int t=toi(s[j]);
            a[t].c[m-1-j]++;
            a[t].t=1;
        }
    }
    for (int i=0; i<A; i++) {
        a[i].v = i;
        a[i].set();
    }
    sort(a,a+A);

    cin >> k;
    for (int i=0; k && i<A; i++)
        if (a[i].v != 35)
            k--, a[i].v=35;

    vec p(N+1,0);
    for (int i=0; i<N; i++) {
        for (int j=0; j<A; j++)
            p[i]+=a[j].c[i]*a[j].v;
        p[i+1] += p[i]/A;
        p[i] %= A;
    }
    for (int i=N; i>=0; i--)
        if (p[i]) {
            while(0<=i)
                cout << toc(p[i--]);
            return 0;
        }
    cout << "0";
}