백준 #1112 진법 변환

일반적으로 우리는 양수 진법 변환에 대해서는 자주 사용했지만, 음수 진법 변환에 대해서는 자주 안 썼죠.

 

base conversion

 

예를 들어서 -10진법이라는 것이 있다면, -10진법 327은 ${327}_{-10}=3\cdot (-10{)}^2+2\cdot (-10)+7=287$이 될겁니다.  그뿐만 아니라 -10진법으로 63은 ${63}_{-10}=6\cdot (-10)+3=-57$이 되어 실제 음수인데, 표현에는 양수가 되기도 합니다.  예외가 좀 있어서인지 문제 난이도는 Gold II이고, 정답비율은 29.6%입니다.

 

이 문제가 음의 진법만 다루었다면 편했을텐데, 양의 진법까지 같이 아우르다보니 귀찮은 것이 많아졌네요.  예를 들어서 10진법 -23은 $-23=(-2)\cdot 10+(-3)$ 으로 각 자리수 자체가 음수값이 됩니다.  표현은 0부터 9까지이지만, 실제 의미는 -9 부터 0까지 표현됩니다.  이게 예외가 됩니다.

 

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

1112번: 진법 변환

 

이 문제를 푸는 핵심은 mod 값을 구하는 것으로 생각했습니다.  양의 진법인 경우에는 무조건 절대값의 수를 이용했습니다.  그래서 mod 값을 구하는 함수를 따로 만들어야 했습니다.

 

int ABS(int n) { return n<0?-n:n; }
int mod(int n, int b)
{
  int r=n%ABS(b);
  if(r<0) r+=ABS(b);
  return r;
}

 

들어온 입력값 n에 대하여서 양의진법인 경우에는 미리 절대값을 취했기 때문에 mod에서 내보내는 값은 반드시 양수가 나와야 합니다.  그래서 위와 같이 음수인 경우에는 진법수를 더해서 양수로 만듭니다.

 

$$n_0=n,d_k=n_{k-1}/b^{k}mod|b|,n_k=n_{k-1}-d_k\cdot b^k$$

 

형태로 수식을 정리할 수 있습니다.

 

틀리기 쉬운 예제를 들자면 다음과 같습니다.

0 3
=> 0

-9 -3
==> 1200

999999999 -2
==> 1001100111011111101111000000011

-11 3
==> -102

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------
//  baekjoon #1112 - Base -10
//    - by Aubrey Choi
//    - created at 2020-01-03
//----------------------------------------------------------
#include <stdio.h>

int ABS(int n) { return n<0?-n:n; }
int mod(int n, int b)
{
  int r=n%ABS(b);
  if(r<0) r+=ABS(b);
  return r;
}
int base(int n, int b, char r[])
{
  int na=b>0?ABS(n):n, t; int c=0;
  while(na) { t=mod(na,b); na=(na-t)/b; r[c++]=t+'0'; } 
  if(!c) r[c++]='0'; r[c]=0;
  return (b>0&&n<0);
}
void print(char r[], int m)
{
  int i;
  if(m) putchar('-');
  for(i=1;r[i];i++);
  for(i--;i>=0;i--) putchar(r[i]); putchar('\n'); 
}
int main()
{
  int n, b, m; char r[64];
  scanf("%d%d",&n,&b);
  m = base(n, b, r);
  print(r, m);
}