BOJ - 1527번 금민수의 개수(C++)

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

문제 난이도

Silver 1(solved.ac 이용)

문제 접근법

4와 7로 이루어진 숫자만 찾으면 된다.
그럼 해당 숫자에 4와 7만 붙여서 범위가 넘지 않으면 4와 7로 이루어진 숫자가 된다.

통과 코드

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int A, B;
int ans;

void dfs(int s, int cnt) {
	if (cnt >= 10) return;
	if (s > B) return;
	if (s >= A) ans += 1;
	dfs(s*10 + 4, cnt+1);
	dfs(s*10 + 7, cnt+1);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> A >> B;
    dfs(0, 0);
	cout << ans << "\n";
	return 0;
}

피드백

시도 1.
처음엔 걍 string으로 받아 string 속에 4와 7 빼고의 수가 발견되면 수 count만 안해주면 된다고 생각했다. 그래서 다음과 같이 짰는데 시간초과가 떴다.

Source code 1

char num[8] = { '0','1','2','3','5','6','8','9' };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int A, B;
	cin >> A >> B;
	int cnt = 0;
	bool flag = true;
	for (int i = A; i <= B; i++) {
		flag = true;
		string N = to_string(i);
		for (int j = 0; j < 8; j++) {
			if (N.find(num[j]) != -1) {
				flag = false;
				break;
			}
		}
		if (flag) cnt++;
	}
	cout << cnt << "\n";

	return 0;
}

시도 2.
DFS를 사용했는데 틀렸습니다

Source code 2

int A, B;

int dfs(int s, int cnt, int ans) {
	if (cnt >= 10) return 0;
	if (s > B) return 0;
	if (s >= A) ans += 1;
	int ansTmp = ans;
	ans += dfs(s*10 + 4, cnt+1, ans);
	ans += dfs(s*10 + 7, cnt+1, ansTmp);
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> A >> B;
	cout << dfs(0, 0, 0) << "\n";
	return 0;
}

반환형 DFS로 생각하고 짜니깐 처음엔 1,10을 넣었을 때 3이 나왔다. dfs 함수로 들어가면서 ans값을 더해주는 거 때문에 기대한 값보다 크게 나온 걸 깨달았고 중간에 tmp 변수를 줘서 기존 ans를 저장했다. 그래도 4초대에서 틀렸습니다가 떴다.

다른 사람 코드를 보니깐 dfs 시작 애초에 ans=0을 주고 들어가니깐 맞았습니다가 떴다. 그 전에 void dfs로 해서 맞았지만 반환형 dfs로 하니깐 적절하게 코드 구성하기 어려웠다.
이 부분에 대해 좀 더 고민하고 문제를 마무리해야겠다.