백준 21275 폰 호석만 Kotlin (완전 탐색)

문제 출처 : https://www.acmicpc.net/problem/21275

21275번: 폰 호석만

문제

폰 호석만은 진법 변환의 달인이다. 어떤 진법의 수가 주어져도 모든 다른 진법으로의 변환이 가능한 폰 호석만은 새로운 문제를 내기로 했다. 폰 호석만이 내는 문제는 다음과 같이 진행된다.

먼저 폰 호석만은 수 3개 X, A, B를 결정한다(0 ≤ X < 263, 2 ≤ A ≤ 36, 2 ≤ B ≤ 36, A ≠ B). 이 때 X는 10진법이다. 그 다음에 X를 A진법으로 표현한 수와 B진법으로 표현한 수를 종이에 써 놓는다.

그 다음에 종이에 써져 있는 두 개의 수를 여러분에게 보여주게 된다. 주어진 두 개의 수를 통해 원래 숫자인 X, A, B를 계산해주자. 만약 조건을 만족하는 (X, A, B)로 가능한 조합이 여러 개라면 "Multiple"을 출력하고, 가능한 조합이 없다면 "Impossible"를 출력한다.

입력

첫번째 줄에 X를 A진법으로 표현한 값과 X를 B진법으로 표현한 값이 공백으로 구분되어 주어진다. 각 자리수는 0 이상 z 이하이다. a부터 z 는 10부터 35 를 의미한다.

단, 0을 제외한 각 수는 0 으로 시작하지 않으며, 길이는 최대 70 이다.

출력

만약 문제의 조건에 맞는 X, A, B가 유일하게 존재한다면, X를 십진법으로 표현한 수와 A와 B를 공백으로 나누어 출력하라. 만약 만족하는 경우가 2가지 이상이라면 "Multiple"을, 없다면 "Impossible"을 출력하라.

제한

• 0 ≤ X < 263
• 2 ≤ A ≤ 36
• 2 ≤ B ≤ 36
• A ≠ B
• X는 0 혹은 양의 정수, A와 B는 양의 정수이다.

알고리즘 분류

• 수학
• 브루트포스 알고리즘

풀이

완전 탐색으로 진법 변환의 경우의 수를 구하는 문제이다.

1번 예제 ep jh를 보자

ep를 a, jh를 b라고 할 때,

a의 최소 진법은 e<p로 25(p)가 된다.

b의 최소 진법은 j>h로 19(j)가 된다.

 

이제 a가 25~36진법일 때, x값이 같은 b의 진법을 19~36진법 사이에서 찾으면 된다.

impossible, mutliple 등의 결과는 분기 처리로 가려낼 수 있다.

 

진법 변환은 ep를  32진수라고 하면, 14(e)*32^1 + 25(p)*32^0 = 473이 나오게 되는 것이다.

 

 

코드

val br = System.`in`.bufferedReader()
//최대 2^63 Long
//a에서 큰 숫자 ~35진법
//b에서 큰 숫자 ~35진법
//이중 포문
var X =-1L
var A=-1
var B=-1
fun main() = with(System.out.bufferedWriter()){
    //input
    val input = br.readLine()
    var minA=0
    var minB=0
    var max=0
    for(ch in input){
        if(ch.isDigit()){
            max = max.coerceAtLeast(Character.getNumericValue(ch))
        }
        else {
            max = max.coerceAtLeast(ch - 'a' + 10)
        }
        if(ch==' '){
            minA=max+1
            max=0
        }
    }
    minB = max+1
    val (a,b) = input.split(' ')

    //solve
    for(i in minA .. 36){
        var x=0L
        for(ch in a){
            if(ch.isDigit()){
                x = x*i + Character.getNumericValue(ch)
            }
            else{
                x = x*i + (ch-'a'+10)
            }
        }
        //long 벗어난 경우
        if(x<0L) break

        //b구하기
        label@for(j in minB .. 36){
            if(i==j) continue
            var y=0L
            for(ch in b){
                if(ch.isDigit()){
                    y = y*j + Character.getNumericValue(ch)
                }
                else{
                    y = y*j +(ch-'a'+10)
                }
                if(y>x) break@label
            }
            
            if(x==y){
                if(X!=-1L){
                    write("Multiple")
                    close()
                    return
                }
               X=x
               A=i
               B=j
            }
        }
    }
//outpu
    if(X==-1L){
        write("Impossible")
    }
    else{
        write("$X $A $B")
    }

    close()
}