백준 #1036 36진수

이번 문제는 꽤 난이도가 높은 문제입니다.  오늘 날짜의 맞은 사람은 143명, 정답률 16.7% 문제네요.  저도 한번 틀렸습니다 나왔네요.

물론 따지고 들면 복잡한 알고리즘이 들어가는 문제는 아닙니다.  풀고나서 생각해보면 당연한 것인데 틀리는 것들이죠.

 

36진수는 0부터 9까지 숫자와 A부터 Z까지 문자를 합쳐서 표현할 수 있는 진법입니다.  사용할 일은 없는 진법이긴 하지만, 파이썬에서는 36진법까지 표현 가능합니다.  파이썬으로 푼다면 쉽게 풀지도 모르겠네요.

 

문제 링크는 아래와 같습니다.

https://www.acmicpc.net/problem/1036

1036번: 36진수

이 문제는 정렬, 문자열 처리, 그리고 큰 수 처리까지 고려해주어야 합니다.

 

N개의 36진법 문자열을 입력받고, 그 수 중, K개의 숫자(0~9, A~Z)들을 Z로 바꿀 때 합이 가장 크게 만들때 그 합을 36진법으로 표현하여라입니다.

 

제가 구상한 알고리즘은 다음과 같습니다.

숫자별로 36진법을 저장할 수 있는 배열을 생성하고 0으로 그 숫자를 채웁니다.

N개의 36진법 문자열을 입력받습니다.

각 자릿수의 문자열에 대하여 배열에 해당 자릿수에 맞는 곳을 1증가시킵니다.

그런후 숫자 c에 저장된 36진법수와 Z-c 를 곱한값을 가지고 증가하지 않는 순으로 정렬합니다.

사실 정렬은 상위 k개만 구하면 됩니다.  (선택정렬을 이용해도 될 듯 합니다만, k값이 36까지도 갈 수있으므로 속도가 빠른 정렬이 이왕이면 좋겠죠.)

상위 k개의 숫자들을 Z 숫자로 바꿉니다.

그런후 36진법 합을 구합니다.

 

자료형을 잘 만드는 것이 귀찮았습니다.  36진법이니까 char[*] 배열로 만들면 되고, 입력이 길이 50, 갯수 50개까지 들어오므로 자릿수의 최대 길이는 52이면 됩니다.  \(35 \times 50 < 36*36*36 \)

 

몇가지 입력들에 대해서 제가 풀은 답을 공유합니다.

5
0
0
0
0
0
0
---------------
0

10
ASDFJH
ADSFKAF
DSJFFD
23JH4
2J4H32 
23JH   
LK65
L6KN3
LKN22
LKN 
7
---------------
132ZAQA5

4
ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLM
QWQWQWFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
1234567890ZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ567890
2
---------------
1ZZD4B6D8EZ012345678ACEGIKLNPIIJKLMNPFERSTUV2468A0

 

 

제가 짠 소스는 다음과 같습니다.  더 쉽고 직관적으로 짜고 싶었는데, 36진법 연산을 구현하자보니 귀찮네요.  큰 수와 36진법을 지원하는 파이썬으로 작성했었다면 소스가 많이 간략해졌을 듯 하네요. 

소스는 참고용으로 봐주세요.

 

//------------------------------------------------------------------------------
//  baekjoon #1036 - Base 36
//    - by Aubrey Choi
//    - created at 2019-12-26
//------------------------------------------------------------------------------
#include <stdio.h>
#include <algorithm>

struct Base36 { int c, d[52]; } base[36], r;
void Mul(Base36 &r, const Base36 &a, int m)
{
  for(int i=0,c=0;i<52;i++)
  {
    r.d[i]=a.d[i]*m+c;
    c=r.d[i]/36; r.d[i]%=36;
  }
}
bool cmp(int a, int b)
{
  Base36 ta, tb;
  Mul(ta, base[a], 35-base[a].c);
  Mul(tb, base[b], 35-base[b].c);
  for(int i=51;i>=0;i--)
  {
    if(ta.d[i]>tb.d[i]) return true;
    if(ta.d[i]<tb.d[i]) return false;
  }
  return false;
}
int main()
{
  int i, j, n, k, t, c, idx[36];
  for(i=0;i<36;i++) base[i].c=i, idx[i]=i;
  scanf("%d",&n);
  while(n--)
  {
    char s[56];
    scanf("%s",s);
    for(k=0;s[k];k++) s[k]=(s[k]<'A')?s[k]-'0':s[k]-'A'+10;
    for(t=0,i=k-1;i>=0;i--,t++) base[s[i]].d[t]++;
  }
  std::sort(idx,idx+35,cmp);
  scanf("%d",&k);
  for(i=0;i<k;i++) base[idx[i]].c=35;
  for(i=0,c=0;i<52;i++)
  {
    for(j=0,t=c;j<36;j++) t+=base[j].c*base[j].d[i];
    r.d[i]=t%36; c=t/36;
  }
  for(i=51,t=0;i>=0;i--)
  {
    if(t||r.d[i]||!i) putchar(r.d[i]<10?r.d[i]+'0':r.d[i]+'A'-10),t=1;
  }
  putchar('\n');
}