본문 바로가기
백준/백트래킹

[백준🥈2] #15663 N과 M(9), #15666 N과 M(12) (Python)

by 똥먹는낙타 2023. 2. 14.
728x90
반응형

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

 

15663번: N과 M (9)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

 

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

 

15666번: N과 M (12)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

✔️ 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
반응형

댓글