[백준(BOJ)]15650번 : 15650 N과 M (2) - Python(파이썬) - (실버3, 순열과 조합)

백준 15650 N과 M (2)

풀이 1 (’ ‘.join(map(str, j)))

from itertools import combinations

n, m = map(int, input().split())

numbers = [i for i in range(1, n+1)]

for j in combinations(numbers, m):
    print(' '.join(map(str, j)))
    

(2, 4) 이런식으로 출력되는데 map함수와 join 함수를 써서 출력하면 2 4 이렇게 출력된다.

 

풀이 2 print(*number)

from itertools import combinations

n, m = map(int, input().split())

numbers = [i for i in range(1, n+1)]

for j in combinations(numbers, m):
    print(*j)

더 간단한 출력 방법이다.

 

풀이 3 백트래킹

n, m = map(int, input().split())
numList = [i for i in range(0, n+1)]

index = 0
visited = [False * len(numList)+1)

def backTracking(result):
		
		if len(result) == m:
			print(*result)
			return
		
		for i in range(1, n+1):
				if (visited[i] == False) and (len(result) == 0 or i > result[-1]):
					visited[i] = True
					result.append(numList[i])
					backTracking(result)
					visited[i] = False
					result.pop()

backTracking([])

백트래킹은 조건에 맞는 해를 만들다가 아니다 싶으면 뒤로가서 다른 방법을 만드는 방법이다. 그래서 재귀를 이용해 많이 푼다.

• 백트래킹은 사실 안써봐서, 답을 보았다. 나중에 다시 풀어보도록 하자!