[C++/1527] 금민수의 개수

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

이건 엊그제(5.19)에 풀었던 문제같다. 일단 문제 조건을 보자.

문제는 은민이는 4와 7을 좋아해서 그 숫자들로만 숫자를 만들려고 한다. A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 자연수 중에 금민수의 것의 개수를 출력해보자.

일단 A와 B의 크기는 1 ~ 1,000,000,000 1부터 10억이다. 자 대충 컴퓨터는 1초에 1억번의 연산인데 첨부터 10억까지 가려면 일단 10초가 걸리기 때문에 단순 for문으로는 해결할 수 없고, 그리고 4 또는 7이 나온다면? 하나하나 체크를 해야하는데 그 또한 숫자로 해결하기엔 말도 안된다. 이 문제는 string 타입으로 문제를 해결해야 한다.

그럼 보자, 우리는 무조건 4 또는 7로만 값을 만들어야 하기 때문에, 4 또는 7로 이루어지는 A의 자리수와 B 자리수 사이에 존재하는 문자열을 구해야한다.

그럼 또 생각을 해볼 수 있다. 11 ~ 20 과 같은 입력에서 4와 7은 존재할 수가 없다. 물론 14, 17은 가능하지만 우리가 원하는 44,47,74,77이라는 값은 이 사이에 들어가지 않는다.

하지만, 이런것까지 고려하면서 문제를 풀기엔 너무 귀찮다. 일단 자릿수 안에 허용되는 4 또는 7로 만들수 있는 문자열을 전부 만들어본다.

일단 4,7이라는 두가지를 사용하기 때문에 아무리 많아봐야 시간을 초과하지 않는다. 2 * 2 * 2 * 2 ... * 2 (n = 10) 정도가 되지 않을까?

그래서 나는 DFS처럼 문자열의 길이에 맞는 4 또는 7로 구성되어 있는 문자열 전부를 구하기로 했다. 아래는 정답코드이다. long long을 사용했는데, int는 21억까지이므로 혹시나~ dfs만들때 77억이 나올 수 있기 때문이다~

#include<iostream>
#include<string>
#include<vector>

using namespace std;

vector<string> v;
char arr[2] = {'4', '7'};
string startNumber,endNumber;

void init() {
	cin >> startNumber >> endNumber;
}

void dfs(int cnt, string number){
	
	if(cnt <= endNumber.length()){
		
		v.push_back(number);
		
		for(int i = 0; i < 2; i++){
			number += arr[i];
			dfs(cnt + 1, number);
			number.pop_back();
		}
		
	} else{
		return;
	}
}

int main(){
	init();
	
	string number = "";
	
	for(int i = 0; i < 2; i++){
		number += arr[i];
		dfs(1, number);
		number.pop_back();
	}
	
	int answer = 0;
	for(int i = 0; i < v.size(); i++){
		
		long long number = stoll(v[i]);
		
		if(number >= stoll(startNumber) && number <= stoll(endNumber)){
			answer++;
		}
		
	}
	
	cout << answer;
	
	return 0;
}