[CLASS 4]백준 - 15650번, 15652번, 15654번, 15657번 - N과 M

 

해당 4문제가 모두 N과 M문제이고, 거의 비슷비슷하다.

 

4문제모두 DFS와 itertools를 사용한 방법 두가지로 풀었다.

 

복원 추출,비복원 추출,순서 고려 까지 모두 itertools에 구현되어 있다는 점에 놀랐다.

 

역시 Python...

 

15650번

# DFS
def dfs(length,number):
    if length == m:
        print(*result)
        return
    for temp in range(number,n+1):
        result.append(temp)
        dfs(length+1,temp+1)
        result.pop()

result = []
n,m = map(int,input().split())
dfs(0,1)

from itertools import combinations
n,m = map(int,input().split())
for case in combinations(range(1,n+1),m):
    print(*case)

 

15652번

# DFS
def dfs(length,number):
    if length == m:
        #print('ho')
        print(*result)
        return
    for temp in range(number,n+1):
        result.append(temp)
        dfs(length+1,temp)
        result.pop()

result = []
n,m = map(int,input().split())
dfs(0,1)

from itertools import combinations_with_replacement
n,m = map(int,input().split())
for case in combinations_with_replacement(range(1,n+1),m):
    print(*case)

 

15654번

# DFS
def dfs(length):
    if length == m:
        print(*result)
        return
    for temp in l:
        if temp not in result:
            result.append(temp)
            dfs(length+1)
            result.pop()

result = []
n,m = map(int,input().split())
l = sorted(list(map(int,input().split())))
dfs(0)

from itertools import permutations
result = []
n,m = map(int,input().split())
l = sorted(list(map(int,input().split())))
for case in permutations(l,m):
    print(*case)

 

15657번

# DFS
def dfs(length,idx):
    if length == m:
        print(*result)
        return
    for i in range(idx,n):
        result.append(l[i])
        dfs(length+1,i)
        result.pop()

result = []
n,m = map(int,input().split())
l = sorted(list(map(int,input().split())))
dfs(0,0)

from itertools import combinations_with_replacement
n,m = map(int,input().split())
l = sorted(list(map(int,input().split())))
for case in combinations_with_replacement(l,m):
    print(*case)