[Baekjoon] 15650번 N과 M (2)
Updated:
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
- 고른 수열은 오름차순이어야 한다.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제
Example 1:
Input:
3 1
Output:
1
2
3
Example 2:
Input:
4 2
Output:
1 2
1 3
1 4
2 3
2 4
3 4
Example 3:
Input:
4 4
Output:
1 2 3 4
조건
시간 제한 : 1초
메모리 제한 : 512 MB
풀이과정
풀이 1
재귀를 이용한 브루트포스 방식으로 해결하였다.
n, m = map(int, input().split())
check = [False]*(n+1)
answer = []
def dfs(index, start):
if index == m:
print(" ".join(map(str,answer)))
return
else:
for i in range(start, n+1):
if check[i]:
continue
check[i] = True
answer.append(i)
dfs(index+1, i+1)
answer.pop()
check[i] = False
dfs(0,1)
풀이 2
n, m = map(int, input().split())
answer = []
def dfs(index, selected):
if selected == m:
print(" ".join(map(str,answer)))
return
else:
for i in range(index, n+1):
answer.append(i)
dfs(i+1, selected+1)
answer.pop()
dfs(1, 0)
풀이 3
n, m = map(int, input().split())
answer = []
def dfs(index, selected):
if selected == m:
print(" ".join(map(str,answer)))
return
else:
if index > n:
return
answer.append(index)
dfs(index+1, selected+1)
answer.pop()
dfs(index+1, selected)
dfs(1, 0)
Leave a comment