[백준] 2877번 4와 7 C++

문제 출처: https://www.acmicpc.net/problem/2877

2877번: 4와 7

K의 값이 10억까지 들어올 수 있어 브루트 포스로 접근하면 시간 초과가 발생할 것이다.

규칙을 찾기위해 정답을 나열해본다.

4, 7, 44, 47, 74, 77, 444, 447, 474, 477, 744,...

4와 7을 0과 1로 대응시켜보면 다음과 같은 규칙이 보인다.

0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100,...

1칸짜리 2^1개,

2칸짜리 2^2개,

3칸짜리 2^3개 순으로 증가한다.

 

K에 2^1, 2^2, 2^3 순으로 계속 빼기를 한다면,

언젠가 K <= 0이 될 것이다.

마지막으로 2^n을 뺐을 때 음수 혹은 0이 나왔다면 n자리로 구성되는 수임을 알 수 있다.

K에 2^n 더해서 값을 되돌려주고 K-1을 2진수로 변경하고 길이가 n이 아닌 경우 0을 채운다.

그 후 0은 4로 1은 7로 변경하여 출력하면 된다.

 

EX)

K = 10

K = K - 2^1  ---> K = 8

K = K - 2^2  ---> K = 4

K = K - 2^3  ---> K = -4 

K가 음수가 되었기 때문에 마지막 2^n을 더해서 돌려준다. K= K + 2^3 = 4 , K는 n 즉 3자리로 구성됨을 알 수 있다.

K-1을 이진수로 변경하면 11이 된다. 현재 길이가 2이기 때문에 길이가 3이 될 때까지 0으로 채운다.

11 --> 011 이후 0은 4로 1은 7로 변경한다.  011 --> 477

 

최적화를 위해 이진수 변환 함수를 작성할 때 0과 1을 4와 7로 바로 변환해주는 방식으로 작성했다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<stack>

using namespace std;



vector<char> tran(int a) {
	vector <char> temp;
	if (a == 0)temp.push_back('4');

	while (a != 0) {
		if (a % 2)temp.push_back('7');
		else temp.push_back('4');
		a /= 2;
	}
	
	return temp;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	

	int K;
	cin >> K;
	int a = 2;
	int cnt = 1;
	vector<char> ans;

	while (true) {
		K -= a;

		if (K <= 0) {
			ans = tran(K + a - 1);
			while (ans.size() != cnt)ans.push_back('4');
			break;
		}
		else{
			a *= 2;
			cnt++;
		}
	}

	reverse(ans.begin(), ans.end());
	for (int i = 0; i < ans.size(); i++)cout << ans[i];


}