BOJ : 1526 가장 큰 금민수

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

4와 7로 만 이루어진 숫자를 구하면 된다.

이런 DP문제도 있는데 경우의 수가 아닌 N이하의 가장 큰 수만 구하면 되기 때문에 완전탐색으로 해결 가능

1의 자리수 4, 7에서 부터 하나씩 4와 7을 붙여 나가도록 하자.

1 : 4, 7

2 : 44, 47, 74, 77 

3 ....

이런 식으로 .

include <cstdio>
#include <queue>
using namespace std;
int main(){
    int N,ans=0;
    queue<int> q;
    scanf("%d",&N);
    if(4 <= N){
        ans=4;
        q.push(4);
    }
    if (7 <= N){
        ans=7;
        q.push(7);
    }
    while(!q.empty()){
        int n=q.front();
        q.pop();
        n*=10;
        if(n+4 <=N){
            ans = n+4;
            q.push(n+4);
        }
        if(n+7 <=N){
            ans = n+7;
            q.push(n+7);
        }
    }
    printf("%d\n",ans);
}