백준 2877번 4와 7 // C++

문제

 

창영이는 4와 7로 이루어진 수를 좋아한다. 창영이가 좋아하는 수 중에 K번째 작은 수를 구해 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 K(1 ≤ K ≤ 109)가 주어진다.

출력

첫째 줄에 창영이가 좋아하는 숫자 중 K번째 작은 수를 출력한다.

 

---

 

풀이

 

규칙을 찾기 위해서 K번째 수를 적다보니까 2진수와 같다는 것을 알게 되었다.

 

달라진 점은 0과 1이 아닌 4와 7로 표현을 해야하며, K + 1의 수를 2진법으로 변환한 뒤 제일 앞자리를 제외한 수를 나타내야 한다.

 

예를 들어, 4번째 수는 5를 2진법으로 변환한 101에서 제일 앞자리 수인 1을 제외하고 나머지 01을 각각 4와 7로 표현한 47이 정답이 된다.

 

---

 

코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> v;

void to_binary(int num);

int main() {
	int num;
	cin >> num;

	to_binary(num + 1);

	for (int i = 1; i < v.size(); i++) {
		if (v[i] == 0)
			printf("4");
		else
			printf("7");
	}
}

void to_binary(int num) {
	vector<int> temp;

	while (num >= 1) {
		temp.push_back(num % 2);
		num /= 2;
	}

	for (int i = temp.size()-1; i >= 0; i--) {
		v.push_back(temp[i]);
	}
}