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

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

 

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

15649번: N과 M (1)

15649 N과 M(1)

 

접근 방법

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

 

 

풀이코드

n, m = map(int, input().split())

s = []

def dfs():
    # 배열의 길이가 m이 되는 경우 해당 리스트 내의 숫자들을 join 메서드를 활용하여 출력 후 해당 dfs 종료
    if len(s) == m:
        print(" ".join(map(str, s)))
        return

    # for 문으로 반복
    for i in range(1, n + 1):
        # 만약 i가 리스트 s안에 존재하지 않는다면 삽입을 해주고 dfs를 호출한다.
        # 해당 dfs가 출력 된 후 가장 뒤에 들어온 i를 pop하여 제거해준다.
        if i not in s:
            s.append(i)
            dfs()
            s.pop()

dfs()