[백준] 2877_4와 7 C++

02 Jan 2024 in Study on Coding Test

수학적 관찰력 및 창의력을 요구했던 문제

정답제출코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> vec;

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

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

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

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

	ToBinary(N + 1);

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

일일이 탐색을 하는 것은 최대 값이 10억이기 때문에 시간초과가 날 것이 뻔했다.

그런데 생각을 해보니 규칙이 2진수와 같다는 것을 알게 되었다.

차이점은 1과 0이 아닌 4와 7로 표기하는 것이지

4와 7로 표기된 수가 몇번째로 큰지는 결국 이진수로 변환하면 몇번째냐와 같은 것이다.

그래서 위와 같이 코드를 구현하고 출력하도록 했다.

이걸 생각해내는 과정이 어려웠던 것 같다.