[BaekJoon] "완전탐색" - 백준 18511번 문제 : 큰 수 구성하기

[문제 설명]

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

18511번: 큰 수 구성하기

 

N보다 작거나 같은 자연수 중에서, 집합 K의 원소로만 구성된 가장 큰 수를 출력하는 프로그램 작성

N = 657이고, K={1,5,7}일 때 답은 577임

 

[해결 로직]

- DFS 재귀 방법으로 풀이하였음

- 먼저 첫번째 원소부터 재귀를 시작

- 1 다음에 1을 붙여주고, 다시 재귀로 들어갔다가 1 붙여주고,

- 만약 조건에 안맞으면 재귀 탈출, 그리고 1 붙인거를 pop.해줌

- 이게 같은 숫자가 들어가줘도 되니깐 안에서 주어진 k 배열에 대해 재귀를 계속 도는 거임

- 만들어진 숫자가 N보다 작고, 현재까지 만든 숫자중에 제일 크다면 탈출

 

[Solution 코드]

n, k = map(int, input().split())
ary = list(map(int, input().split()))
max_sum = -999999
n_lnt = len(str(n))

def dfs(ary, sol):
    global max_sum
    #print(sol)

    if len(sol) > n_lnt:
        return

    if len(sol) > 0:
        num_str = int(''.join(map(str, sol)))

        if (num_str <= n) & (num_str >= max_sum):
            max_sum = num_str

    for i in range(k):
        sol.append(ary[i])
        dfs(ary, sol)
        sol.pop()

# numbers = [1, 2, 3]
# string_numbers = ''.join(str(num) for num in numbers)
# print(string_numbers)  # 결과: "123"

dfs(ary, [])
print(max_sum)

 

탐색은 재밌는것 같다 ! 하면 할 수록!