| 시간 제한 | 메모리 제한 |
| 초 | MB |
문제
N보다 작거나 같은 자연수 중에서, 집합 K의 원소로만 구성된 가장 큰 수를 출력하는 프로그램을 작성하시오. K의 모든 원소는 1부터 9까지의 자연수로만 구성된다.
예를 들어 N=657이고, K={1, 5, 7}일 때 답은 577이다.
입력
첫째 줄에 N, K의 원소의 개수가 공백을 기준으로 구분되어 자연수로 주어진다. (10 ≤ N ≤ 100,000,000, 1 ≤ K의 원소의 개수 ≤ 3) 둘째 줄에 K의 원소들이 공백을 기준으로 구분되어 주어진다. 각 원소는 1부터 9까지의 자연수다.
단, 항상 K의 원소로만 구성된 N보다 작거나 같은 자연수를 만들 수 있는 경우만 입력으로 주어진다.
출력
첫째 줄에 N보다 작거나 같은 자연수 중에서, K의 원소로만 구성된 가장 큰 수를 출력한다.
풀이
K의 원소들을 오름차순으로 정렬해서 하나씩 붙여가며 N보다 커지면 탐색을 중단하고 되돌아간다. 가장 컸던 값만을 계속해서 return 하면 간단하게 해결 될 것 같은걸?
매 탐색마다 현재 탐색 중인 수 n을 매개변수로 받고, 현재 탐색에서 가장 큰 수 ret으로 정해둔다. 만약 n > N이라면 탐색하지 않아야 하며, n을 반환해서는 안되기 때문에 0을 반환해 가장 작은 값을 이전 탐색으로 되돌려준다.
탐색이 가능하다면 n에 10을 곱하고 K의 원소를 하나씩 뽑아 더해주며 다음 깊이로 탐색을 시도한다. 탐색 결과를 ret과 비교해 더 큰 값으로 바꿔준다.
이 과정을 반복하면 가장 깊은 탐색까지 도달했을 때 가장 큰 ret만이 연쇄적으로 반환된다.
정답 코드
import sys
input = sys.stdin.readline
miis = lambda: map(int, input().split())
def solution():
N, K = miis()
num = sorted(list(set(miis())))
# n은 현재 탐색 중인 수
def dfs(n):
ret = n # n을 가장 큰 값으로 지정
if n > N: return 0 # n이 N보다 큰 경우는 0을 반환
for m in num: # K의 원소들을 하나씩 확인
# 다음 깊이로 탐색을 시도하고,
# 반환된 값과 ret을 비교해 더 큰 값을 저장
ret = max(ret, dfs(n * 10 + m))
return ret # 탐색 결과를 반환
print(dfs(0)) # 0으로부터 출발
solution()
