728x90
반응형
https://www.acmicpc.net/problem/15663
https://www.acmicpc.net/problem/15666
✔️ Code (N과 M (9))
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
nums = list(map(int, input().split()))
visited = [False] * n
nums.sort()
result = []
def backtracking(k):
if k == m:
print(*result)
return
remember = 0
for i in range(n):
if not visited[i] and remember != nums[i] :
visited[i] = True
result.append(nums[i])
remember = nums[i]
backtracking(k+1)
visited[i] = False
result.pop()
backtracking(0)
✔️ Code (N과 M (12))
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()
result = []
def backtracking(k, start):
if k == m:
print(*result)
return
visited = [False] * n
remember = 0
for i in range(start, n):
if not visited[i] and remember != nums[i]:
visited[i] = True
result.append(nums[i])
remember = nums[i]
backtracking(k+1, i)
visited[i] = False
result.pop()
backtracking(0, 0)
✏️ Comment
remember 변수를 이용해서 중복되는 수열이 만들어지지 않게 확인해야 하고, N과 M (12) 같은 경우에는 visited 함수를 백트래킹 함수 안에서 매번 초기화해줌으로써 (7, 7) (9, 9) 같은 수열도 만들어지도록 고려해야 한다.
728x90
반응형
'백준 > 백트래킹' 카테고리의 다른 글
[백준🥇5] #1759 암호 만들기 (Python) (0) | 2023.02.27 |
---|---|
[백준🥈2] #14889 스타트와 링크 (Python) (0) | 2023.02.15 |
[백준🥈3] #15649 N과 M(1) (Python) (0) | 2023.02.09 |
[백준] #15650 N과 M (2) (python) (0) | 2022.06.23 |
[백준] #15649 N과 M (1) (python) (0) | 2022.06.23 |
댓글