(C++) - 백준(BOJ) 1526번 : 가장 큰 금민수 답

www.acmicpc.net/problem/1526

1526번: 가장 큰 금민수

dfs로 모든 경우의 수를 탐색하는 문제였습니다.

 

 

풀이방법

  2의 7승(100만의 자릿수 + 1) 정도로 dfs를 수행하면 됩니다.

Code

 

#include <bits/stdc++.h>
using namespace std;
int n,ans;
void dfs(int sum){
    if (sum > n) return;
    dfs(sum * 10 + 7);
    dfs(sum * 10 + 4);
    ans = max(ans, sum);
}

int main(){
    cin >> n;
    dfs(0);
    cout << ans;
}

Test Case

 몇 가지 반례를 직접 작성해 보았습니다. 

 

input

7000

 

답 4777

 

input

4

답 4

 

input

7

답 7