1036. 36진수

문제 번호랑 내용을 맞춘 건지?

1036번: 36진수

---

36진수는 0~9, A~Z를 사용하여 숫자를 표현한다. A는 10, B는 11, ..., Z는 35를 나타낸다. 36진수 $N$개가 주어질 때, 36진수 숫자(0~9, A~Z) 중 $K$개를 골라서 주어진 N개의 수에 존재하는 그러한 숫자를 모두 Z로 바꾼 후 $N$개의 수의 합을 구한다. 가능한 합의 최댓값을 구하시오.

..고르라고 해서 진짜 다 골라보면 안 된다. 고를 수 있는 방법이 최대 $\left(\begin{array}{c}36\\ 18\end{array}\right)=9075135300$이므로 절대로 안 된다.

 

조금 수학적으로 생각해 보자. 어떤 숫자를 Z로 바꾸면 전체 합이 증가하는데, 이 증가량을 최대로 하면 전체 합도 최대가 될 것이다. 따라서 먼저 전체 수의 합을 구해놓고, 우리는 어떤 숫자(예를 들어 A)를 Z로 바꿨을 때 증가하는 값이 얼마인지를 전부 구하고, 증가량을 내림차순으로 정렬하여 앞에서부터 $K$개의 값을 더해주면 정답을 얻을 수 있다.

 

단 주의할 점은 $36^{50}=653318623500070906096690267158057820537143710472954871543071966369497141477376$이므로 ``long long``조차 쓸 수 없다. 36진수 연산을 직접 구현하던지, ``BigInt``를 지원하는 언어를 사용하는 게 편하다.

---

문제 자체는 간단하다. 다만 36진수 연산을 직접 구현하기가 꽤 까다롭다. 16진수는 차라리 디버깅이라도 쉽지, 36진수는 다루는 값도 크고 익숙하지도 않아서 제대로 구현한 게 맞는지 확신하기가 어렵다. ``Python``이나 ``Java`` 사용을 권장한다. 하루종일 맞왜틀 하던거 파이썬으로 포팅해서 내니까 맞았습니다!! ....

---

akwdhoxmf

로직이 맞았다는 점에 의의를 두자..