Backtracking

백준 15654번 문제 바로가기 permutations을 이용한 풀이 ‘1부터 n까지의 숫자’ 대신에 ’n개의 숫자’가 주어진다는 점을 제외하면 N과 M (1)과 다를게 없다. ㅇ # 입력 import sys from itertools import permutations n,m = map(int, sys.stdin.readline().split()) arr = sorted(list(map(int, sys.stdin.readline().split()))) # 처리 for ans in permutations(arr, m): print(*list(ans)) backtracking을 이용한 풀이 숫자가 주어진 다는 점만 고려해주면 금세 끝낼 수 있다. # 입력 import sys n,m = map(int, sys.stdin.readline().split()) arr = sorted(list(map(int, sys.stdin.readline().split()))) ans = [] # 처리 def backtrack(): if len(ans) == m: print(*list(map(str, ans))) return for i in arr: if i not in ans: ans.append(i) backtrack() ans.pop() # return이 실행되면 여기로 돌아옴. (전 단계로 돌아감 = backtrack) backtrack()

백준 15656번 문제 바로가기 product을 이용한 풀이 중복순열(product)에 대한 문제. 주어진 숫자를 이용해야한다는 조건 말고는 사실상 N과 M(3)과 동일하다. # 입력 import sys from itertools import product n,m = map(int, sys.stdin.readline().split()) arr = sorted(list(map(int, sys.stdin.readline().split()))) # 처리 for ans in product(arr, repeat=m): print(*list(ans)) backtracking을 이용한 풀이 중복순열도 backtracking을 이용해서 풀어보자! 간단하게 N과 M(5) 풀이에서 for문만 지우면 된다ㅎㅎ # 입력 import sys n,m = map(int, sys.stdin.readline().split()) arr = sorted(list(map(int, sys.stdin.readline().split()))) ans = [] # 처리 def backtrack(): if len(ans) == m: print(*list(map(str, ans))) return for i in arr: ans.append(i) backtrack() ans.pop() # return이 실행되면 여기로 돌아옴. (전 단계로 돌아감 = backtrack) backtrack()

백준 15657번 문제 바로가기 combinations을 이용한 풀이 python에는 중복조합에 대한 라이브러리도 가지고 있다. 바로 combinations_with_replacement 지난 N과 M (1) 해답에서 combinations만 _with_replacement를 붙여주면 간단하게 해결 가능하다. # 입력 import sys from itertools import combinations_with_replacement n,m = map(int, sys.stdin.readline().split()) arr = sorted(map(int, sys.stdin.readline().split())) # 처리 for ans in combinations_with_replacement(arr, m): print(*list(ans)) backtracking을 이용한 풀이 중복조합을 backtracking으로도 풀어보자! 범위 설정에만 조심한다면 간단하게 풀어낼 수 있게 된다. # 입력 import sys n,m = map(int, sys.stdin.readline().split()) arr = sorted(map(int, sys.stdin.readline().split())) ans = [] # 처리 def backtrack(start=0): if len(ans) == m: print(*list(map(str, ans))) return for i in arr[start:]: ans.append(i) backtrack(arr.index(i)) ans.pop() # return이 실행되면 여기로 돌아옴. (전 단계로 돌아감 = backtrack) backtrack()