백준 11576 문제 풀이 python

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

🐒 Base Conversion

베이스? 군사기지 같은건가 했는데

수학에서 숫자를 표현하는 기반이 되는 진법을 Base라고 한다더라.

진법은 수를 셀 때, 자릿수가 올라가는 단위를 기준으로 하는 셈법의 총칭이다

따라서 진법 변환 문제이다.

---

✍ 나의 풀이

a,b = map(int,input().split())

m = int(input())
#m번 반복하라고 준거겠지?

arr = list(map(int,input().split()))
#10진수부터 구할까
arr.reverse()

ten = 0
for i in range(m):
    ten += arr[i]*(a**i)

# b진수 구하기
#나누어 떨어질때까지
result = []
while ten//b:
    result.append(ten%b)
    ten = ten//b
result.append(ten)

result.reverse()
print(' '.join(map(str,result)))

며칠동안 어려운 문제에 후두려맞다가
오랫만에 나의 힘으로 풀 수 있는 문제가 나왔다.

인터넷 도움없이 제출을 누르고 맞았습니다!!가 뜨는 기쁨😽

문제를 다풀고 += 같은 연산자를 뺴놓고 오류가 떠서 당황을 했다.
분명 맞을텐데 왜 이상한 값이 나오나 ㅋㅋ

위 코드에서 주석은 풀면서 내려가다 떠오른 생각들을 적었고 진법 변환 방법을 증명(?) 할려고 공책에 수식도 끄적였다.

---

문제 이해

처음 문제를 보면서 무슨 소리인가 했는데 천천히 구절 하나하나 곱씹으면서 읽어보니 이해는 되었다.

입력
17 8    >> 17진법를 8진법로 바꿔야한다
2		 >> 17진수의 자릿수 
2 16	  >> 바꿔야할 17진수

17진법에서 10진법으로

아니 17진법이면 0x2g 이런 느낌 아닌가? 왜 알파벳이 없지?

2 16이 뭔가 했는데 17진수의 각 자리를 10진수으로 나타낸 느낌? 이다..

10진법에서는 하나의 자릿수에서 10을 넘기면 다음 자릿수에 1을 더하고 현재 자릿수를 0으로 만든다.

9 에 1을 더하면 1 0 이 되는 것처럼.
1 0 에서 첫째자리 0은 0*(10^0)으로 설명할 수 있고
둘째자리 1은 1*(10^1)처럼 설명할 수 있다.

17진수를 자릿수로 생각하면 첫째자리 16*(17^0)
둘째자리 2*(17^1)
모두 더하면 10진법으로 50을 가리키게된다.

10진법으로 바꿨으니 다른 진법으로 바꿔서 나타내야겠다.

원하는 진법으로 변환하기

문제에서는 8진법으로 바꾸라했지만 다양한 진법으로 바꿀 수 있는 방법을 찾기위해
나는 3진법으로 일단 바꾸어보았다.

50을 3로 나누면 몫이 16, 나머지가 2이다. 2를 첫째자리에 놓는다
16을 다시 3으로 나누면 몫이 5 나머지가 1이다. 1을 둘째자리에 놓는다
5를 3으로 또 나누면 몫이 1 나머지가 2이다. 2를 셋째자리에 놓는다
마지막 몫인 1을 넷째자리에 놓는다

50을 3진법으로 나타내면 1 2 1 2가 된다.

솔직히 진법변환을 완전히 이해했다기보단 규칙성이 보였다.

이렇게 3으로 여러번 나누는 이유는 3진법의 자릿수는 3의 거듭제곱으로 이루어졌기 때문이라고 생각한다.

마지막 몫인 1은 결국 50 // 3^3이다.

a,b = map(int,input().split())

m = int(input())

arr = list(map(int,input().split()))
arr.reverse() # 첫째자리부터 계산하기 위해서 뒤집었다.

ten = 0		#각 자릿수를 10진수로 바꾸고 변수에 더해서 저장한다
for i in range(m):
    ten += arr[i]*(a**i) #**은 거듭제곱 표현이다

result = []   #10진수의 진법을 변환하고 저장될 배열이다.
while ten//b:	#몫이 0이 될때까지 반복해서 나눈다.
    result.append(ten%b) #나머지를 배열에 추가한다.
    ten = ten//b
result.append(ten) #마지막 몫을 배열에 추가한다.

result.reverse() #첫째자리가 맨뒤에 있어야하므로 뒤집는다
print(' '.join(map(str,result)))