[BOJ] 1526 가장 큰 금민수

1. 문제 링크

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

2. 문제 해설

이 문제는 4와 7로 이루어진 수 중에서 주어진 수 보다 작은 가장 큰 수를 찾는 문제이다. 여러 풀이가 있을 수 있지만 필자는 구해놓고, 찾는 방식을 택했다.

1. vector에 4와 7을 push_back 한다.

2. 4에서 나올 수 있는 가지수인 44, 47을 push_back한다.

3. vector 의 그 다음 수를 찾아서 다음으로 나올 수 있는 수를 push_back 한다.

4. 주어진 n보다 커질 때 까지 반복한다.

5. binary search를 사용해서 n보다 작으면서 가장 큰 수를 찾는다.

3. 소스코드

#include<iostream>
#include<string>
#include<stack>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;
#define MAX_NUM 200100

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n, cnt=0;
    vector<int> v;
    cin >> n;
    v.push_back(4);
    v.push_back(7);
    while (v.back() <= n) {
        int cur = v[cnt++];
        cur *= 10;
        v.push_back(cur+4);
        v.push_back(cur+7);
    }
    
    cout << *(upper_bound(v.begin(), v.end(), n)-1) << '\n';
    
    return 0;
}

4. 추가 언급

아래의 코드를 보면 굉장히 BFS 방식과 비슷하지 않는가?

다른 점이 하나 있다면 큐에서 pop을 하지 않으면서 계속 push만 해주는 점이 있겠다. 이렇게 해줌으로써 가능한 모든 경우들을 저장하고 다닐 수  있다. 굳이 이 문제에서 이렇게 다 저장할 필요는 없지만 코드가 간결해지기 때문에 필자는 이렇게 풀었다. BFS로 풀이를 한다면 더 좋은 공간 복잡도를 가지고 문제를 풀 수 있을 것 같다.

BFS로 코드를 짜서 풀면 밑의 코드처럼도 풀 수 있다.

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define fio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;

int main(){
    fio;
    int n, ans = -1;
    int arr[2] = {4, 7};
    queue<int> q;
    cin >> n;
    q.push(4); q.push(7);
    
    if (n < 7) {
        ans = 4;
        goto stop;
    }
    
    while (!q.empty()) {
        int size = (int)q.size();
        for (int i=0; i<size; i++) {
            int cur = q.front(); q.pop();
            for (int j=0; j<2; j++) {
                int next = cur * 10 + arr[j];
                if (next == n) {
                    ans = next;
                    goto stop;
                }
                if (next > n) {
                    ans = q.back();
                    goto stop;
                }
                q.push(next);
            }
        }
    }
    
stop:
    printf("%d\n", ans);
    
    return 0;
}