[C언어,C++] 백준알고리즘 1526번 가장 큰 금민수

boj.kr/1526

 

문제

은민이는 4와 7을 좋아하고, 나머지 숫자는 싫어한다. 금민수는 어떤 수가 4와 7로만 이루어진 수를 말한다.

N이 주어졌을 때, N보다 작거나 같은 금민수 중 가장 큰 것을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 4보다 크거나 같고 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 N보다 작거나 같은 금민수 중 가장 큰 것을 출력한다.

예제 입력 1 복사

100

예제 출력 1 복사

77

 

재귀로 간단하게구현하였다.

N보다 작으면서 값에다가 10을 곱하여 7을더하거나

10을곱하여 4를더함

그러면 먼저 7,77,777, 순으로 탐색할것이며 N이 76일시 77은 N보다크므로 4를더하여 74 가 답이나옴

결과에 가장큰 max값을 res에 저장한다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <math.h>
#include <map>
using namespace std;
int N;
int res = 0;
void DFS(int sum)
{
    if (sum > N)
        return;
    DFS(sum * 10 + 7);
    DFS(sum * 10 + 4);
    res = max(res, sum);
        
}
int main()
{
    cin >> N;
    DFS(0);
    cout << res;
}

 

깃 링크

 

https://github.com/evga7/Practice_Algorithm_01/commit/bb024c75242e235d3a2b465a6f7464653edc2794