[Python] 백준 #18511- 큰 수 구성하기

문제

---

18511번: 큰 수 구성하기

코드

---

My answer

from itertools import product
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
num = list(map(int, input().split()))
a = []

for i in range(len(str(n)), -1, -1):
    a = list(product(num, repeat=i))
    answer = ["".join([str(j) for j in i]) for i in a]
    answer = [int(i) for i in answer if int(i) <= n]
    if (len(answer) > 0):
        print(max(answer))
        break

Another answer

n, k = map(int, input().split())
a = list(map(int, input().split()))
result = 0

def dfs(x):
    global result
    # n보다 작거나 같은 자연수에 대해서만 확인
    if x > n:
        return
    # K의 원소로만 구성된 가장 큰 수를 저장
    result = max(x, result)
    for i in a:
        # K의 원소로만 구성된 모든 수를 탐색
        dfs(x * 10 + i)

dfs(0)
print(result)

풀이

---

우선 내 풀이의 경우, 주어진 숫자로 만들 수 있는 모든 조합을 큰 경우부터 시작했다.

무슨 소린가 하면, 주어진 숫자가 3개일 때 주어진 숫자중 중복을 허용하여 3개를 뽑는 방법부터 1개를 뽑는 방법까지 모두 진행하였다. 숫자를 뽑은후, 그 숫자를 정수형으로 만들어서 해당 숫자가 n보다 작으면 그 즉시 종료했다. 

위의 코드를 똑같은데 for문만 역순이 아니라 순방향으로 진행한다면 runtime error이 걸릴 수도 있다. 답안이 조건을 만족하는 가장 큰 수를 찾는 것이기 때문에 역순으로 시작하여 답안을 찾는 즉시 종료하면 오류를 피할 수 있다.

아래 방법은 dfs를 이용해서 해결한 방법이다. dfs를 이용하여 모든 조합을 거쳐가며 현재 저장된 최대값과 비교해가며 정답을 도출하였다.