[사설] 3이 없는 나라

http://www.judgeon.net/problem.php?cid=1621&pid=4 

Judgeon

#include <stdio.h>
#include <math.h>
int n;
int ans;

void to_deci(void)
{
	for (int i = 0;;) {
		if (n == 0) break;
		int tmp = n % 10;
		if (tmp < 3) ans += tmp * pow(9, i);
		else ans += (tmp - 1) * pow(9, i);		//3이 쓰이지 않았으므로 한 칸씩 당긴다 
		n /= 10;
		i++;
	}
}

void main(void)
{
	scanf("%d", &n);
	to_deci();
	printf("%d", ans);
}

 

사실 위의 사이트에서 푼 문제는 아니지만, 기록하면 좋을 것 같아서 남긴다.

 

 

이 문제는 변형된 진법 문제이다. 9진법(0, 1, 2, 4, 5, 6, 7, 8, 9)인데 9가 아니라 3을 사용하지 않기 때문이다. 

그리고 주의할 점은 n의 크기가 매우 크기 때문에 대부분 생각했을 방법인, 루프를 돌리면서 i = 1부터 n까지의 숫자 중 3이 포함된 것을 제외하는 방법으로 풀면 타임아웃된다.

 

그래서 이 문제는 루프를 돌리되, 2진법을 10진법으로 바꾸는 것 처럼 9진법으로 나타낸 수를 10진법으로 바꿔주어야 한다. 

예컨대 9진법 15는 (5 * (9 * 0)) + (1 * (9 * 1)) 이런식으로 변경할 수 있다.

다만, 이때 주의할 점은 3을 제외했기 때문에 3보다 큰 4, 5, 6, 7, 8, 9 에 대해서는 -1 을 해줘야 한다는 것이다. 따라서 이 문제에서 변형된 9진법 15는 ((5 - 1) * (9 * 0)) + (1 * (9 * 1)) 이다.