백준] 2877 - 4와 7(COCI 2010/2011)

시간 제한 : 1초

메모리 제한 : 128MB

입력

첫째 줄에 K(1<=K<=10^9)가 주어진다.

출력

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

소스코드

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int main(void)
{
	int n, sum = 0, k, idx, i, size;
	cin >> n;
	for (k = 1; k <= 32; k++)
	{
		sum += pow(2, k);
		if (sum >= n)
			break;
	}
	
	idx = n - pow(2, k) + 1;
	vector<int> arr(k, 0);
	i = 0, size = arr.size();
	while (idx>0)
	{
		arr[size - 1 - i] = idx % 2;
		idx /= 2, i++;
	}
	for (int i = 0; i < size; i++)
	{
		if (arr[i] == 1)
			cout << 7;
		else
			cout << 4;
	}
}

Tip

4와 7을 이진수의 0과 1로 생각하고 문제를 접근하면 어렵지 않게 풀어낼 수 있다. 소스가 지저분하긴 하지만, N번째 숫자의 자릿수가 얼마나 될지 계산하는 게 가장 중요하다.