[백준/알고리즘] 6679번 싱기한 네자리 숫자 (브론즈 2)

클릭하면 백준 페이지로 이동합니다.

---

 

BOJ 6679번

 

싱가한 네자리 숫자란, [1000, 9999]인 10진수 숫자 중에서, 다음의 조건을 만족하는 숫자를 말한다.
숫자를 10진수, 12진수, 16진수로 나타낸 다음, 각각의 숫자에 대해 각 숫자의 자릿수를 더한 값이 같은 수이다.
싱기한 네자리 숫자를 모두 출력하시오.

 

풀이 알고리즘 : 구현, 완전탐색

 

문제에 대한 해설을 입력합니다.

 

범위가 작기 때문에 1000 ~ 9999를 모두 10진수, 12진수, 16진수로 표현하고, 각 자릿수를 더하면 된다.

 

구현해야하는 부분은 10진수를 12진수나 16진수와 같은 n진수로 변환하는 방법만 알고 있으면 된다.

 

10진수값을 n으로 계속 나누면서, 이때의 나머지가 각각 n진수일때의 각 자릿수가 된다.

 

n진수로 표현하려면 스택에 나머지들을 넣고, 그대로 pop하면서 출력하면 되지만, 문제에서는 각 자릿수의 합을 구하기 때문에 나눴을 때 나머지들만 카운트해서 더해주면 된다.

 

아래는 10진수를 12진수로 변환하는 예이다.

 

10진수 12진수 변환

 

위와 같은 방법으로 10진수를 12진수, 16진수로 변경하는 함수가 n12, n16 함수이고, 완전탐색으로

 

n10 == n12 == n16 일 때, 해당 숫자를 10진수로 출력하면 된다.

 

소스코드 보기

 

#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))

// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};

int n10(int num10) {
	int i = 1000, cnt = 0;
	while(0 < i) {
		cnt += num10 / i;
		num10 = num10 % i;
		i = i / 10;
	}
	return cnt;
}

int n12(int num10) {
	int cnt = 0;
	while(0 < num10) {
		cnt += num10 % 12;
		num10 = num10 / 12;
	}
	return cnt;
}

int n16(int num10) {
	int cnt = 0;
	while(0 < num10) {
		cnt += num10 % 16;
		num10 = num10 / 16;
	}
	return cnt;
}

int main(void) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	for(int i = 1000; i < 10000; i++) {
		if(n10(i) == n12(i) && n12(i) == n16(i)) {
			cout << i << "\n";
		}
	}

	return 0;
}