[BOJ 15649] N과 M (1)

문지영·2023년 3월 31일
0

CODINGTEST

목록 보기
18/21

문제 15649

풀이

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

N과 M 시리즈의 첫 번 째

백트래킹 문제
arr: 수열이 담긴 리스트
visited[i]: 자연수 i가 담겨있는지 여부

참고: ' '.join(map(str, arr))
arr을 str로 바꾸고 join을 이용하여 원소 사이 공백 한 칸으로 구분하여 출력

정답

def func():
    if len(arr)==M: # 개수가 차면 출력 후 함수 종료
        print(' '.join(map(str,arr)))
        return

    for i in range(1,N+1):
        if not visited[i]: # 중복제거
            arr.append(i)
            visited[i]=True
            func()
            arr.pop()
            visited[i]=False

N, M = map(int, input().split())
arr = []
visited = [False]*(N+1)
func()

제출

profile
BeHappy

0개의 댓글