15650번: N과 M (2)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
나의 풀이
- 수열이 오름차순인지 확인하기 위해서, 정렬 전후가 같은지 체크하는 방식으로 풀었다.
- 답은 맞았지만, 가능성이 없는 수열도 불필요하게 계산된다는 단점이 있다.
def get_num(k):
# 수열이 완성된 경우
if k == m:
if sorted(num_list) == num_list:
print(*num_list)
return
# 수열에 원소 저장
for i in range(1, n + 1):
if not isused[i]:
num_list[k] = i
isused[i] = 1
get_num(k + 1)
# 사용 후 제거
isused[i] = 0
def solution(n, m):
# 숫자 중복 여부 확인
global isused
isused = [0] * (n + 1)
# 현재 수열
global num_list
num_list = [0] * m
get_num(0)
n, m = map(int, input().split())
solution(n, m)- 앞서 언급한 단점을 해결하기 위해서, for문 범위를 [ic]i + 1[/ic] 부터 시작하도록 변경해 불필요한 계산을 없앴다.
def get_num(k, start):
# 수열이 완성된 경우
if k == m:
if sorted(num_list) == num_list:
print(*num_list)
return
# 수열에 원소 저장
for i in range(start, n + 1):
if not isused[i]:
num_list[k] = i
isused[i] = 1
get_num(k + 1, i + 1)
# 사용 후 제거
isused[i] = 0
def solution(n, m):
# 숫자 중복 여부 확인
global isused
isused = [0] * (n + 1)
# 현재 수열
global num_list
num_list = [0] * m
get_num(0, 1)
n, m = map(int, input().split())
solution(n, m)