백준 1527 금민수의 개수 (C++)

https://www.acmicpc.net/problem/1527

#include <iostream>
#include <vector>

using namespace std;

int a, b, ans;

void gold(long long k){

    if (k > 1000000000) {
        return;
    }

    if (k >= a && k <= b) {
        ans++;
    }

    gold(k * 10 + 4);
    gold(k * 10 + 7);

}


int main() {

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

    cin >> a >> b;


    gold(4);
    gold(7);


    cout << ans;

    return 0;
}

1. 문제

a, b의 10억 이하의 두 자연수가 주어진다. 이 때, a 이상 b 이하이면서, 4와 7로만 구성되어 있는 수의 개수를 구하라.

2. 풀이

처음에는 a와 b 사이에 있는 모든 수를 두고 조건에 맞는 지 확인했으나 이렇게 되면 최대 10억번의 연산이 일어나므로 시간초과가 일어난다. 따라서 반대로 조건에 맞는 수를 먼저 구하고, 이 수가 범위 내에 있는지 확인해야 한다.

void gold(long long k){

    if (k > 1000000000) {
        return;
    }

    if (k >= a && k <= b) {
        ans++;
    }

    gold(k * 10 + 4);
    gold(k * 10 + 7);

}

이를 확인하는 로직이다. k가 해당 범위에 있다면 세어주고, 해당 숫자의 뒤에 4, 7을 각각 붙여주어 이를 구한다.

int main() {

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

    cin >> a >> b;


    gold(4);
    gold(7);


    cout << ans;

    return 0;
}

조건에 해당하는 가장 작은 수는 한 자리 수들이므로 이를 넣어준다. 연산이 끝나고 ans를 출력하면 답을 구할 수 있다.