728x90
반응형
18511번: 큰 수 구성하기 (acmicpc.net)
문제
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
✔️ Code
from itertools import product
n, k_num = map(int, input().split())
len_max = len(str(n))
k = list(input().split())
while True:
tmp = list(product(k, repeat = len_max)) #repeat를 통해 몇 개를 뽑을지 결정
result = []
for i in tmp:
if int("".join(i)) <= n:
result.append(int("".join(i)))
if len(result) >= 1:
print(max(result))
break
else:
len_max -= 1
✏️ Comment
- 이 문제는 product로 푸는 경우가 많은 것 같아서 나도 product 풀이를 참고했다. product는 중복 순열을 구하는 것이라고 한다. 예를 들어서 앞의 문제에서 썼던 combination의 경우 (a, b, c) 중 2개를 고를 때 (a, b) (a, c) (b, c) 로 경우의 수가 총 3개가 나오는데 product는 (a, a) (a, b) (a, c) (b, a) (b, b) (b, c) (c, a) (c, b) (c, c) 이렇게 9가지가 존재한다. 그 차이를 잘 알아두면 좋을 것 같다.
- 간과했던 점이 하나 있는데 풀이에서 (””.join) 을 사용해서 이를 int형으로 바꿔 n과 비교하는 부분이 있다. 이를 위해서 처음에 k의 수를 입력 받을 때 int 형이 아닌 str 형태로 입력 받아야 하는데 int로 입력 받아서 타입에러가 발생했었다.
728x90
반응형
'백준 > 정렬, 탐색' 카테고리의 다른 글
[백준🥈4] #17626 Four Squares (python) (0) | 2022.07.18 |
---|---|
[백준🥈3] #2503 숫자 야구 (python) (1) | 2022.07.18 |
[백준🥈5] #2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (python) (0) | 2022.07.14 |
[백준🥈5] #1969 DNA (python) (0) | 2022.07.13 |
[백준] #15721 번데기 (python) (0) | 2022.07.13 |
댓글