[7일차](문제 번호 : 11005, 진법 변환 2) 도전 -1

1. 문제 요약

10진법 수 N이 주어진다.

N을 B진법 수로 변환하여 출력하면 된다.

10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다.

A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35

 

예시.

입력

60466175 36

출력

ZZZZZ

---

2. 풀어보기

먼저, 오늘 글의 제목이 -1인 이유가 있다.

이 문제를 아직 해결하지 못했기 때문이다!!..

학교 행사인지라 12시 이전에는 글을 올려야하는데, 10시 반쯤에 시작해서, 몇 십분동안 고민을 해봤지만, 오류는

피할 수 없었다. (심지어 오류의 원인도 찾지 못했다..)

 

따라서, 오류가 났지만 알고리즘 자체는 맞는 것 같기에.. 올려보도록 한다.

 

서론이 길었다. 이 문제는 어제의 문제와 정반대의 문제로, 왠지 int() 함수를 사용해 역전환시키는 기능이 있을 것 같았지만, 수학적 사고방식으로 풀어보기로 하였다.

 

1. N, B 입력받고, N을 B진법 수로 변환했을 때, 그 수의 길이 예측하기.

2. 나머지 계산을 활용하여 B진법 수의 앞자리 수부터 찾아가기

3. B진법 수의 한 자리수가 10 이상일 때 알파벳으로 변환하는 과정 거치기

---

3. 코드

1. N, B 입력받고, N을 B진법 수로 변환했을 때, 그 수의 길이 예측하기.

 

N, B = map(int, input().split())
for i in range(30):
    if N < B**i:
        M = i
        break

예를 들어, N = 2*36^3 + 35*36^2 + 10*36^1 + 8*36^0 = 139040 일 경우,

N < 36^4 이다. (왜냐하면, 최댓값이라 볼 수 있는 35*36^3 + 35*36^2 + 35*36^1 + 35*36^0  = 36^4 -1 (등비수열의 합)

에 의해, 절대적으로 성립한다.)

즉 i를 1씩 키워가며 N < B**i 인 순간, i는 B진법 수로 변환했을 때의 수의 길이가 된다.

 

또한, range의 숫자가 30인 이유는 2^30 > 10억이기 때문이다. (문제의 조건에서 N은 10억 이하임을 명시함.)

---

2. 나머지 계산을 활용하여 B진법 수의 앞자리 수부터 찾아가기

BBase = []
if M != 0:
    for i in range(M)[::-1]:
        for j in range(37):
            if N - j*B**i < 0:
                BBase.append(j-1)
                N -= (j-1)*B**(i)
                break
else:
    BBase = [0]

BBase는 B진법 수의 각 글자들의 리스트이다.

M = 0인 경우, 즉, N = 0인 경우, B가 뭐든 간에 B진법 수로 변환시 0이므로 0을 리스트에 넣는다.

0이 아닌 경우, M을 큰 쪽부터 작은 쪽순으로 읽는다.

예를 들어, N = 2*36^3 + 35*36^2 + 10*36^1 + 8*36^0 = 139040 일 경우,

N < 3*36^3 이다. (2*36^3 뒤 쪽의 항들의 합이 항상 36^3 보다 작기 때문이다. (위의 등비수열 논리와 같음))

즉 j를 1씩 키워서 N - j*B**1 < 0 인 순간, j-1이 B**i의 계수이다.

 

---

3. B진법 수의 한 자리수가 10 이상일 때 알파벳으로 변환하는 과정 거치기

for i in BBase:
    if i >=10 :
        BBase[BBase.index(i)] = chr(i+55)
    else:
        BBase[BBase.index(i)] = str(i)
        
BBase = ''.join(BBase)
        

print(BBase)

저번에도 많이했던, ord과정의 역순이다. 또한, join함수는 str에만 사용가능하기 때문에,

정수인 i부분은 str로 바꾸어준다.

 

---

4. 문제점

채점시 NameError를 띄운다..

IDLE에서 반례를 찾아보려 했지만, 도저히 찾을 수가 없어.. 반례를 찾거나 코드의 논리적 오류부분, 허점을 찾으면 바로 다음 글을 작성하도록 하겠다.