[백준 | 실버5] 18511번:큰 수 구성하기(백트랙킹)

문제

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의 원소로만 구성된 가장 큰 수를 출력한다.

 

풀이

 - 메모리 초과난다 ㅠㅠ 조금 더 줄여야할거같다

import sys
#sys.stdin = open("input.txt", "r")

def DFS(L, sum) : 
    global max_num
    if L == k :
        s = ''
        for i in range(k) :
            s += str(result[i])
        if n >= int(s) and max_num <= int(s):
            max_num = int(s)

    else :
        for i in range(k) :
            result[L] = arr[i]
            DFS(L+1, result)

n, k = map(int, input().split())
arr = list(map(int, input().split()))
check = [0] * n
result = [0] * k 
max_num = 0

DFS(0, 0)

print(max_num)

 

풀이 2

 - max값을 찾았을때 max_num 반환하고 중지(더이상 찾지 않는다.)

 - max값을 찾지 못한 경우 None 반환

 - 풀이1의 코드 같은 경우 1, 5, 7의 수중 n이 1655이면 1577을 반환해야 하는데 777을 출력하여 사이즈 수정

import sys
sys.stdin = open("input.txt", "r")

def DFS(L, result) : 
    m = len(result)
    if L == m :
        s = ''
        for i in range(m) :
            s += str(result[i])
        if n >= int(s) :                #n보다 작고, max_num보다 큰 값
            return int(s)

    else :
        for i in range(k) :
            result[L] = arr[i]              #result[i]에 값 넣기
            max_num = DFS(L+1, result)       #다음 가지로 뻗기
            if max_num is not None:         #max값일때 max_num 반환
                return max_num
    return None                             #max값이 아닌 경우 None 값 반환

n, k = map(int, input().split())
num_size = len(str(n))
arr = list(map(int, input().split()))
arr.sort(reverse=True)                      #큰 숫자부터 찾기

data = DFS(0,  [0] * num_size)

if(data is None):                           #1000이면 3자리 숫자 나와야하므로 None이면 3자리수 계산
    data = DFS(0,  [0] * (num_size-1))
print(data)