완전탐색(유형정리) - 백준 18511

18511번: 큰 수 구성하기 (acmicpc.net)

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

예제 입력 1 복사

657 3
1 5 7

예제 출력 1 복사

577

 

문제는 위와 같다. 예시를 보게 되면, N이 657일 경우 집합 K = {1,5,7} 인 상태에서 N을 넘지 않는 수 중 3개의 숫자를 합쳐서 만들 수 있는 가장 큰 수가 577이므로 577을 출력하게 된다. 이를 통해 보면 7이 중복적으로 들어가고 있는 것을 볼 수 있다. 그렇다면 여기서 우리가 떠올릴 것은 중복순열일 것이다. 

 

이를 통해 중복순열 product를 사용하자는 생각을 가지고 문제에 접근해보자.

 

N과 K 갯수를 각각 입력받고, K 원소 집합을 입력받는다. 가장 큰 수를 뽑아내기 위해서는 N의 길이만큼 중복적으로 뽑는 것이 바람직하므로 product의 인수를 K집합 속에서 N길이만큼 뽑아낸다. 이제 이를 조합하여 N을 넘지 않는 선에서 answer 리스트에 append 시켜준다.

 

마지막으로 answer 길이가 1이 넘는 상황, 즉 모든 중복조합으로 만들어진 원소들이 차 있는 상황에서 max 값을 print 하면 끝. 그렇지 않은 경우 N 길이만큼 조사할 K_length 변수를 하나씩 줄여준다. 

from itertools import product
N, K_number = map(int, input().split())

K = list(map(int, input().split()))
K_length = len(str(N))

while(True):
    temp = list(product(K, repeat = K_length))
    answer = []
    for i in temp:
        num = int(''.join(map(str, i)))
        if num <= N:
            answer.append(num)
    if len(answer) >= 1:
        print(max(answer))
        break
    else:
        K_length -= 1

 

이 문제는 문자열과 숫자를 잘 구분해야 하는 문제로, 강제형변환을 매우 잘 이용해야한다. 계속 형변환 문제들 때문에 오류가 났고, 형식을 맞추는 과정에서 꽤 시간을 소모했다.