백준 1526번 [가장 큰 금민수](C++) -yes6686- 티스토리

백준 문제 풀이: 1526

---

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

문제 설명:

금민수란 숫자의 모든 자릿수가 4와 7로만 이루어진 수를 뜻합니다. 주어진 자연수 n 이하의 가장 큰 금민수를 구하는 문제입니다.

---

문제 해결 코드

// 가장 큰 금민수 문제의 최적화된 코드
#include <iostream>
#include <string>
using namespace std;

bool isGoldMinNumber(int num) {
    // 숫자를 문자열로 변환하여 금민수 여부를 확인
    string s = to_string(num);
    for (char c : s) {
        if (c != '4' && c != '7') return false; // 금민수가 아님
    }
    return true; // 금민수
}

int main() {
    ios::sync_with_stdio(false); // 입출력 속도 향상
    cin.tie(NULL);

    int n;
    cin >> n;

    for (int i = n; i >= 4; i--) { // n부터 4까지 역순 탐색
        if (isGoldMinNumber(i)) { // 금민수 여부 확인
            cout << i << '\n';
            break;
        }
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 숫자를 문자열로 변환해 각 자릿수를 검사하여 금민수 여부를 판단합니다. 주어진 숫자 n에서 4까지 역순으로 탐색하며 가장 큰 금민수를 찾습니다.
• 구현 세부사항:
• isGoldMinNumber: 숫자를 문자열로 변환하고, 각 자릿수가 4와 7로만 이루어졌는지 검사하는 함수입니다.
• 메인 루프에서는 n부터 시작하여 4까지 역순으로 숫자를 검사합니다. 가장 큰 금민수를 발견하면 즉시 출력 후 종료합니다.
• 시간 복잡도 분석:
• 최악의 경우, n부터 4까지 모든 숫자를 확인하므로 시간 복잡도는 O(n * d)입니다. 여기서 d는 숫자의 최대 자릿수입니다.
• 금민수를 빠르게 찾는 구조이므로 실제 실행 시간은 n의 크기에 따라 효율적입니다.

---

결과

위 코드는 입력 n에 대해 가장 큰 금민수를 정확하고 효율적으로 구합니다. isGoldMinNumber 함수를 별도로 구현하여 가독성을 높였으며, 역순 탐색으로 불필요한 연산을 최소화했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!