[Python] 백준 알고리즘 15650번 - N과 M(2)

[Python] 백준 알고리즘 15650번 - N과 M(2)

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

15650번: N과 M (2)

 

n과 m(2)

 

접근 방법

n과 m(1)과 동일한 접근이다. 하지만 중복은 없어야 한다는 게 문제의 조건이다. https://skyriv312079.tistory.com/63

[Python] 백준 알고리즘 15649번 - N과 M(1)

 

따라서 문제의 접근은 비슷하지만 코드를 조금 다르게 작성해야한다.

예제 답안

문제의 예제 답안을 보면 1을 한번 회전 후에는 다음 수에는 1이 등장하지 않는다. 그래서 DFS를 입력받을 때 시작점을 파라미터로 입력받는 식으로 진행을 하였다.

 

1. 숫자 입력 → 문제의 요구사항 입력
   1. n. m 입력 / 정답 기록용의 s 리스트 생성
2. 메서드 구현
   1. 주어진 n까지 중복 없이 m개를 골라 출력
      1. 리스트 s의 길이가 m과 동일해지면 해당 반복문을 멈추고 출력 후 종료
         1. join 및 map 활용
      2. 동일하지 않은 경우 for 반복문 실행( start ~ n + 1까지), i는 반복문에 할당된 변수
         1. 정답 기록용 배열의 리스트에 만약 i가 없다면 i를 추가 = 같은 수가 들어가는 것을 방지 
         2. 해당 DFS 메서드 실행, 해당 메서드 실행 시 시작점을 i+1로 갱신하여 넣어준다
            1. 해당 DFS에서 반복문은 start가 갱신되어 진행이 된다.
         3. 재귀 호출된 메서드가 종료 후 s 리스트 안에 존재하는 원소를 pop

 

 

풀이 코드

'''
1부터 n까지 자연수 중에 중복없이 m개
'''


def DFS(start):
    if len(s) == m:  # 해당 배열의 길이가 m과 동일해지면 프린트 후 리턴
        print(' '.join(map(str, s)))
        return

    # 반복문 반복시
    for i in range(start, n + 1):
        if i not in s:
            s.append(i)
            DFS(i+1)
            s.pop()


n, m = map(int, input().split())
s = []
DFS(1)