[Python] BOJ - N과 M 시리즈

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

15650번: N과 M (2)

# N과 M (1) 문제에서 중복된 수열들을 출력하지 않고, 각 수열은 오름차순이어야 하는 조건이 추가된 문제이다.

 

# prev변수를 통해 중복된 수열을 출력하지 않는 방법은 다음과 같다.

   ex) 처음에 prev가 0이므로 for문에서 comb에 1을 넣고 BT(1, 1, [1])을 호출한다.

        BT(1, 1, [1])에서 prev가 1이므로 for문에서 i가 2부터 N-1까지 돈다.

        따라서 comb에 이미 1이 있을 때 1이 또 comb에 들어오지 않게 한다.

        또한, comb가 처음에 2로 시작할 때(이미 answer에 [1,2]가 있음) [2,1]과 같이 만들어지지 않게 해준다.

 

N, M = map(int,input().split())
answer = []
def BT(length, prev, comb):
	# 종료 조건
	if length == M:
		answer.append(comb.copy())
		return
	
	for i in range(prev, N + 1):
		# prev변수를 통해 중복된 중복된 수열 출력하지 않기
		if i in comb:
			continue

		# 재귀 호출	
		comb.append(i)
		BT(length + 1, i, comb)
		comb.pop()

	return answer

BT(0, 1, [])
for i in answer:
	print(*i)

(solved.ac 티어: 실버 3)

 

=================================================================

 

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

15651번: N과 M (3)

# N과 M (2)문제와 비슷한데, 같은 수를 여러번 골라도 된다.

 

N, M = map(int,input().split())
answer = []
def BT(length, comb):
	if length == M:
		answer.append(comb.copy())
		return

	for i in range(1, N+1):
		comb.append(i)
		BT(length + 1, comb)
		comb.pop()
BT(0, [])
for i in answer:
	print(*i)

(solved.ac 티어: 실버 3)

 

=================================================================

 

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

15652번: N과 M (4)

# N과 M (4)문제이다.

 

N, M = map(int,input().split())
answer = []
def BT(num, prev, letters):
	if num == M:
		answer.append(letters.copy())
		return

	for i in range(prev, N+1):
		letters.append(i)
		BT(num + 1, i, letters)
		letters.pop()
BT(0, 1, [])
for i in answer:
	print(*i)

(solved.ac 티어: 실버 3)