[Beginner][정올] 3106번 : 진법변환

[Beginner][정올] 3106번 : 진법변환 

JUNGOL

 

 

[풀이 후기]
난이도 : ★☆☆☆ (Beginner)
문제 종류 : 진법 변환
해결 방법 : Horner's Method

 

* 난이도 구분
★☆☆☆ (Beginner) : 알고리즘 적용만으로 해결 가능
★★☆☆ (Advanced) : 알고리즘을 활용하여 구현해야 해결 가능
★★★☆ (Pro) : 알고리즘을 활용한 구현 + 최적화 아이디어로 해결 가능
★★★★ (Expert) : Pro보다 발전된 최적화 아이디어로 해결 가능

---

 

문제

 

 

 

 

문제분석

1. 0≤​ S를 10진수로 바꾼수 ≤​ 2^63-1 이므로, A가 2진법이라고 할 때, 최대 64길이의 수가 입력될 수 있다. 
2. A진법에서 B진법으로 어떻게 변환할지 고민해보자. 

 

 

---

 

접근 방법

이 문제의 핵심은 "어떻게 A진법에서 B진법으로 변환할 것인가?" 이다. 

 

 

결론부터 이야기하면, 아래의 과정을 거치면, 변환이 가능하다. 

1. A진법 수를 10진법으로 바꾼다. 
2. 10진법 수를 B진법으로 바꾼다. 

 

 

 

진법을 변환할 때에는 Horner's Method (호너의 법칙) 를 이용하면 된다. 

수학적인 설명은 위키백과에 나와있다. 

출처 : 위키백과

 

 

수학이 어려우니, 우리는 2진법을 10진법으로 바꾸는 예를 들어서 확인해보자. 

왼쪽은 숫자로 예시를 든 것이고, 오른쪽은 코딩으로 옮긴 것이다. 

    char S[4] = { 1, 1, 0, 1 };
    int d = 0;
    for (int i = 0; i < 4; i++) {
        d = d * 2 + S[i];
    }

 

 

 

 

 

* 문제를 풀다보면, 이런 형태의 코드를 종종 볼 수 있는데, 이는 주로 Data의 압축을 위한 진법 변환에서 사용된다. 

for (int i = 0; i < 4; i++) {
    d = d * 2 + S[i];
}

 

---

 

코드

#include <stdio.h>

int A, B;
char S[100];

char toChar(int d) {
    if (d < 10) return d + '0';
    else return d + 'A' - 10;
}

void dToB(long long d) {
    if (d < B) {
        printf("%c", toChar(d));
        return;
    }

    dToB(d / B);
    printf("%c", toChar(d % B));
}

int main() {
    while (scanf("%d %s %d", &A, S, &B) && A) {	// A=0 이면, 종료
        long long d = 0;	// 10진법 수

        for (register int i = 0; S[i]; i++) {   // A진법 S를 10진법으로 변환
            if (S[i] < 'A') d = d * A + (S[i] - '0');
            else d = d * A + (S[i] - 'A' + 10);
        }

        dToB(d);    // 10진법 d를 B진법으로 변환
        puts("");
    }
    return 0;
}

 

 

 

---

 

제출 결과

정올 제출 결과