[BOJ/Step14] 15652 : N과 M (4) (Python)

www.acmicpc.net/problem/15652

15652번: N과 M (4)

---

1~N 중 M개의 수를 골라 비내림차순으로 출력하는 문제

 

(1) 리스트에 미리 m개만큼의 0을 저장한 후 index 순서대로 채워넣으며 출력하는 방법

  def sequence( seq, n, m, index ) :

    1. i가 seq[index-1] ~ N까지 반복 => 이전 위치(왼쪽)의 수보다 큰 수만. 비내림차순으로 출력해야하고 이미 나왔던 수열일 것이기 때문

    2. 리스트 seq[index]에 i 대입

    3. index+1 == m이면 seq를 출력

    4. 아니면 sequence( seq, n, m, index+1 ) 호출

# 15650-1.py

def sequence(seq, n, m, index):
    for i in range(seq[index-1] if seq[index-1] != 0 else 1, n+1):
        seq[index] = i
        if index + 1 == m:
            print(' '.join(map(str, seq)))
        else:
            sequence(seq, n, m, index+1)


n, m = map(int, input().split())
nm = [0 for _ in range(m)]
sequence(nm, n, m, 0)

 

(2) itertools 모듈의 combinations_with_replacement함수를 이용하는 방법

# 15650-2.py

import itertools

n, m = map(int, input().split())
nm = [str(i) for i in range(1, n+1)]

a = list(itertools.combinations_with_replacement(nm, m))
for i in a:
    print(' '.join(i))

 

위부터 (2) (1)번 코드

왜인지 이번엔 시간이 비슷하다

모듈 함수를 비슷하게 코드가 짜진걸까 ? ㅎㅎㅎ