[백준 15650 실버3] N과 M (2)

www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

해결방안

• 대표적인 백트래킹 문제

• 기본적인 조합에 대한 이해가 있으면 좀 더 쉽게 풀 수 있음

알고리즘

1. n, m을 받아옴

2. m 크기 만큼의 배열을 초기화 해서 생성
   1. 즉, 전체 필요한 길이 만큼의 배열을 0으로 일단 초기화
3. index와 cnt를 인자로 가지는 함수 정의
   1. index는 시작지점을 뜻함. 조합의 경우 이전에 갔었던 곳을 다시 재방문 하면 안되기 때문에 시작지점을 뜻하는 index부터 다시 반복문 시작
   2. cnt는 현재의 위치를 뜻함. 변경되어야 하는 값의 위치를 뜻함
   3. 배열의 cnt 위치에 i + 1의 값을 넣어줌
   4. 정의한 함수를 인자에 i + 1, cnt + 1을 넣어 재귀로 다시 실행 
   5. cnt가 현재 원하고자 하는 조합의 길이와 일치할 경우 출력하고 함수 종료

핵심 팁

• 순열 문제에는 visited라는 함수를 이용해서 재귀 함수 전과 후에 방문 처리를 변경하였지만, 여기서는 그럴 필요가 없음
  • 어차피 index부터 시작하기 때문에 굳이 체크할 필요가 없음
• 코드로만 보기 보다는 그림을 그려보며 함수를 따라가보면 조금 더 이해가 쉬움
• 백트래킹 방식 말고 라이브러리를 이용해도 가능
  
  • from itertools import combinations

 

# 조합문제
n, m = map(int, input().split())
arr = [0] * m
def comb(index, cnt):
    if cnt == m:
        print(" ".join(map(str, arr)))
        return
    # 처음부터가 아닌 그 자리부터 다시 시작 함으로써 조합 가능하게 해줌
    for i in range(index, n):
        arr[cnt] = i + 1
        comb(i + 1, cnt + 1)
        # 순열에서는 visited가 필요하지만 조합에서는 필요 없음
        # visited[i] = False
comb(0, 0)

 

 

*퍼가신다면 출처와 댓글 부탁드립니다.

*더 많은 자료는 아래 github에 있습니다

https://github.com/griffinGC/Algoritm_PS

https://github.com/griffinGC/TIL_Public