[백준 Java] 1036 36진수

문제 링크

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

 

풀이

이해하고 푸는데 한참 걸렸다. 진짜.. 진짜 오래 걸렸다 진짜...........

 

36진법으로 변환할 때 0-9, A-Z에서 해당하는 자리수를 Z로 변환했을 때 가장 큰 차이가 나는 것을 선택해야 한다.

말로 풀어서 설명하기 어려운데, 예를 들어서 예제의 HELLO는 다음과 같이 표현할 수 있다.

H	17 * 36^4
E	14 * 36^3
L	21 * 36^2 + 21 * 36^1
O	24 * 36^0

이것을 Z로 변환했을 때 차이가 가장 큰 값을 찾으려면 아래와 같이 변환하면 된다.

H	(35-17) * 36^4
E	(35-14) * 36^3
L	(35-21) * 36^2 + (35-21) * 36^1
O	(35-24) * 36^0

따라서 0-9, A-Z 값을 저장할 배열을 만들어주고, 해당 인덱스에 맞게 위의 표에 맞게 자리수를 넣어준다.

배열을 정렬해주고 난 후 가장 차이가 큰 수를 K개 더해준다.

 

간단한 예로 들면,

a = 1
b = 2
z = 10

a + b = 3 //총 합으로 사용

z - a = 9
z - b = 8

이때 a를 선택한다.

총합에 z-a의 차이를 더해주면 a + b -> 3 + (z - a) = 3 + 9 = 12가 된다.

위와 같은 예시로 N만큼 입력을 받고 36진수로 변환해서 일단 모든 숫자의 총합을 구해준다.

Z로 변환했을 때 가장 큰 차이를 가지는 상위 K개가 가지고 있는 차이값을 총합에 더해주면 구하고자 하는 최대값이 된다.

따라서 어떤 문자를 바꿀 것인지는 몰라도 된다.

 

자바의 long 타입은 50자를 받지 못하기 때문에 BigInteger를 사용한다.

질문게시판에서 반례를 참고했다

2
99999999999999999999999999999999999999999999999999
1
1

답
100000000000000000000000000000000000000000000000000

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        //0) 초기화
        // 0-9, A-Z의 36진수 값을 저장할 배열 설정
        BigInteger[] digit = new BigInteger[36];
        Arrays.fill(digit, BigInteger.ZERO); //초기화

        //총합
        BigInteger sum = BigInteger.ZERO;

        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            BigInteger cur = new BigInteger(str, 36); //36진수로 변환

            //1) 각 36진수를 총합에 더해줌
            sum = sum.add(cur);

            //2) 한글자씩 Z로 변환했을 때 가중치를 저장
            //ex) YZ라면, digit[Y] += (35 - Y) * 36^1을 저장함
            BigInteger pow = BigInteger.ONE; //지수 값
            for (int j = str.length() - 1; j >= 0; j--) {
                int idx = str.charAt(j) <= '9' ? str.charAt(j) - '0' : str.charAt(j) - 'A' + 10; //digit에 저장할 인덱스 설정
                digit[idx] = digit[idx].add(pow.multiply(BigInteger.valueOf(35 - idx)));
                pow = pow.multiply(BigInteger.valueOf(36)); //다음 자리수로
            }
        }

        //3) digit을 정렬하고 내림차순으로 사용해서 K만큼 더해줌
        //ex) 1+2 = 3을 10+2=12로 변경했을 때, 10-1의 차이인 9만큼 더해줘야 총 합이 됨
        int K = Integer.parseInt(br.readLine());
        Arrays.sort(digit);
        int cnt = 0;
        for (int i = 35; i >= 0 ; i--) {
            if(cnt == K) break;
            sum = sum.add(digit[i]);
            cnt++;
        }

        //4) 출력
        System.out.println(sum.toString(36).toUpperCase());

    }

}

처음에는 하나하나 전부 36 -> 10 -> 36 변환해가면서 구했는데 로직 자체가 틀렸었다.

이런 수 연산같은걸 생각해야 하는 문제가 아직도 어렵다...