[백준] 15650번 N과 M(2)

사용 언어 - Python3

15650번: N과 M(2) (실버3, DFS 백트래킹 문제)

문제 ★LG CNS 21년 상반기 코테랑 유사★

15650번: N과 M (2)

 

정답

DFS 백트래킹 재귀함수 조합 문제 !! 15649,15450,15651,15652번은 세트로 공부

• 아래 백트래킹 문제 링크를 첨부합니다.

(정답 풀이) 15649번에서 start 포인트만 지정해주면 되는 문제

똑같은 구조로 back() 함수를 진행하지만, 다음 재귀함수를 시작할 때 start 포인트를 한개씩 증가시켜준다.

15649번의 경우, [1 2] != [2 1]

15650번의 경우, [1 2] == [2 1]

# 정답1
N, M = map(int,input().split())
ans = []

def back(start):
  if len(ans) == M :
    print(" ".join(map(str,ans)))
    return
  for i in range(start,N+1):
    if i not in ans:
      ans.append(i)
      back(i+1)
      ans.pop()

back(1)

 

정답2의 아이디어!

itertools의 combinations 파이썬 내장함수를 이용한다.

itertools.permutations(array,수열길이) = 1부터 N까지 중복되지 않은 M개 길이의 수열을 만든다.

itertools.combinations(array,수열길이) = permutations에서 [1 2] == [2 1]의 경우를 제외한 수열을 만든다.

 

출력 형식에 좀 더 신경써줘야하는 방법이었다.

 

array = [1, 2, 3]
permutations(array, 2) => [1,2], [1,3], [2,1], [2, 3], [3, 1], [3, 2]
combinations(array, 2) => [1,2], [1,3], [2,3]

#정답2 - 내장함수 이용
import itertools

N, M = map(int, input().split())
arr = list(itertools.combinations([i for i in range(1,N+1)],M))
for i in arr:
    answer=""
    for j in i:
        answer+=str(j)
        answer+=" "
    print(answer)

---

레퍼런스

• 백준 백트래킹 15649,15450,15651,15652번은 세트로 공부해야한다.

백트래킹 문제 비교

• • 15649번 중복X 수열
  • 15650번 중복X 시작포인트 지정 수열
  • 15651번 중복O 수열
  • 15652번 중복O 시작포인트 지정 수열
  
  
  • 15649번 [1 2] [1 3] [1 4] [2 1] [2 3] [2 4] [3 1] [3 2] [3 4] [4 1] [4 2] [4 3]
  • 15650번 [1 2] [1 3] [1 4] [2 3] [2 4] [3 4]
  • 15651번 [1 1] [1 2] [1 3] [1 4] [2 1] [2 2] [2 3] [2 4] [3 1] [3 2] [3 3] [3 4] [4 1] [4 2] [4 3] [4 4]
  • 16652번 [1 1] [1 2] [1 3] [1 4] [2 2] [2 3] [2 4] [3 3] [3 4] [4 4]

백트래킹 단계

• 정답 참고 

[BAEKJOON 백준] 15650 N과 M (2) (PYTHON)

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부