백준 15652 N과M(4) 파이썬

백준 15652번 N과 M(4) 풀이

접근방식

1. m개의 숫자가 채워질 리스트(arr)를 생성한다.
2. 방문한 숫자를 체크해줄 visited 리스트를 생성한다.
   = > 바로 이전 문제와 다른 점은 방문처리 리스트가 불필요하다는 것이다.
3. dfs 라는 함수를 만들어서 재귀함수를 활용하여 depth를 계산한다.
4. depth == m이라면 arr 리스트에 저장된 숫자를 출력하도록 한다.
5. 비내림차순으로 출력하기 위해서, i를 start인자에 넣어 재귀함수를 실행한다.

# 입력받기
import sys

input = lambda: sys.stdin.readline().rstrip()

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

# 길이만큼 저장할 임시 리스트 생성
arr = []

def dfs(depth, start):
  # 길이와 일치할 경우 결과값 출력
    if depth == m:
        print(' '.join(map(str, arr)))
        return
    for i in range(start, n):
      # 같은 숫자가 출력되어야 하므로 방문처리 리스트 불필요
        arr.append(i+1)
      # 비내림차순 출력을 위해 i를 start인자에 넣어주기
        dfs(depth+1, i)
        arr.pop()
dfs(0,0)

해당 문제는 실버3레벨에 해당하므로 어렵지 않게 풀 수 있는 문제였습니다.

백트래킹과 재귀함수를 입문하기에 최적의 문제집이라고 생각해서

N과M 시리즈를 꼭 여러번 풀어보시는 것을 추천드립니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.

Just do it & Keep steady