[브론즈 1] 백준 1526 - 가장 큰 금민수 (파이썬)

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

풀이

금민수란 숫자는 4또는 7로만 이루어진 수이다. 입력으로 주어지는 N이하의 수 중에서 가장 큰 금민수를 출력하는 문제이다.

결국, 1~6자리의 모든 금민수를 생성하고, 그중 N이하인 것 중 가장 큰 수를 찾는다.

이 문제는 6자리 이하의 숫자만 고려하면 되므로, 완전탐색으로 충분히 해결 할 수 있다.

for i in range(1, 7):  # 자릿수: 1~6자리
    for j in range(i + 1):  # 7을 넣을 자리 개수
        for combination in combinations(range(i), j):
            kms = 0
            for k in range(i):
                kms *= 10
                if k in combination:
                    kms += 7
                else:
                    kms += 4
            A.append(kms)

i 는 현재 자릿수를 나타내며, j의 경우 그 중에서 7이 들어갈 자리 개수를 나타낸다. 콤비네이션을 통해서 자릿수 중 어떤 자리에 7을 넣을지를 조합으로 생성하고, 나머지 자리는 4로 채운다. 각 조합에 따라 금민수를 만들고 A에 저장한다.

사실 DFS 또는 순열/중복순열 방식으로 생성하는 것이 더 직관적일 수 있다.

코드

# 백준 1526 - 가장 큰 금민수
# 분류 : 브루트포스
 
from itertools import combinations
 
N = int(input())
 
A = []
for i in range(1, 7) :
    # [0, 1, 2, ..., i - 1]
    for j in range(i + 1) :
        for combination in combinations(list(range(i)), j) :
            kms = 0
            for k in range(i) :
                kms *= 10
                if k in combination :
                    kms += 7
                else :
                    kms += 4
            A.append(kms)
 
answer = -1
for a in A :
    if a <= N :
        answer = max(answer, a)
 
print(answer)