[코딩테스트 29일차] BAEKJOON 11005번 : 진법 변환 2

[BAEKJOON 11005번 : 진법 변환 2]

[문제]

---

[고찰]

해당 문제를 처음에 접근할 때는, 출력값 'ZZZZZ'에 정신이 팔려 "N - x * B⁰ - x * B¹ - x * B² ⋯의 식을 만족하는 x를 찾은 뒤, x를 아스키코드를 활용해 문제의 조건에 따라 출력하려고 했습니다.

 

그런데 생각해보니, x의 값이 일정한 것은 예제 입력에서만 그런 것이고, 실제 입력값에서 x는 일정하지 않고, 각 진법의 자리 수마다 모두 다른 값일 수 있기 때문에 이 아이디어는 사용하지 못하였습니다.

 

그리고 이후에 다른 아이디어는 생각을 하지 못하겠어서 다른 분들의 풀이를 찾았고, 해당 문제에 대한 답변을 정리하고자 합니다.

---

[개념]

해당 문제에서 쓰는 아이디어는 나머지와 몫을 이용하는 것입니다.

 

어떤 수 N을 B진법으로 바꾸고 싶을 때는 아래와 같이 표현할 수 있습니다.

N = a₀ × B⁰ + a₁ × B¹ + a₂ × B² + ... + aₖ × Bᵏ

 

여기서 a₀, a₁, a₂, ..., aₖ 은 진법 변환 후의 각 자릿수입니다

 

이걸 반대로 생각한다면,

• a₀ = N % B  → 가장 낮은 자리 (B⁰)의 숫자
• N = N / B     → 다음 자리 계산을 위해 N을 한 자릿수 위로 줄임
• a₁ = N % B  → B¹ 자리 숫자
• N = N / B …
• …

이걸 반복하면서 나머지를 계속 저장하면, 자동으로 모든 자리 수의 숫자를 구하는 것이 가능합니다.

---

 

예제 입력의 값 60466175를 위의 방식대로 하면 아래와 같습니다.

단계	나눈 몫	나머지	진법 자리 (역순)
1	1679615	35	Z (B⁰ 자리)
2	46656	35	Z (B¹ 자리)
3	1296	35	Z (B² 자리)
4	36	35	Z (B³ 자리)
5	1	35	Z (B⁴ 자리)

 

 

---

이를 코드로 구현하면 다음과 같습니다.

while (N > 0) {
	int remainder = N % B;

	if (remainder < 10)
	{
		result += (char)(remainder + '0');
	}
	else
	{
		result += (char)(remainder - 10 + 'A');
	}

	N /= B;
}

---

[정리]

이런 아이디어는 경험에서 나오는 것 같습니다.

지금까지 브론즈의 문제들을 풀어왔는데, 하루 정도만 더 브론즈 문제를 풀고,

앞으로는 실버 문제를 풀면서 더 넓은 폭의 문제를 풀어야겠습니다.

---

[Solution]

#include <iostream>
#include <string>
#include <algorithm> 

using namespace std;

int main()
{
    int N, B;
    cin >> N >> B;

    string result = "";

    while (N > 0)
    {
        int remainder = N % B;

        if (remainder < 10)
        {
            result += (char)(remainder + '0');
        } else
        {
            result += (char)(remainder - 10 + 'A');
        }

        N /= B;
    }

    if (result.empty()) 
        result = "0";

    reverse(result.begin(), result.end());

    cout << result;
    
    return 0;
}