[15650] N과 M (2)

15650번: N과 M (2)

 

www.acmicpc.net

 

---

🤔 문제 설명

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열은 오름차순이어야 한다.

 

🤨 제한 사항

• 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

• 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

• 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

😀 입출력 예

입력	출력
3 1	1 2 3

입력	출력
4 2	1 2 1 3 1 4 2 3 2 4 3 4

입력	출력
4 4	1 2 3 4

 

👩‍🔧 사용 메서드 및 속성

sys.stdin.readline()	사용자로부터 한 줄의 입력을 받습니다.
datetime	파이썬에서 날짜와 시간을 조작하는 기능을 제공합니다.
map()	배열의 각 원소에 연산을 수행합니다.
len()	문자열이나 배열 등의 길이를 반환합니다.
from itertools import combinations	파이썬에서 지원해주는 조합용 외장 함수입니다.

 

👩‍🏫 어떻게 풀어요?

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열은 오름차순이어야 한다.

 

순열과 조합의 차이를 아시나요?

 

• 순열 : n개의 원소를 사용해 순서를 정하고 r개의 배열로 나타냅니다. 순서가 존재하기 때문에 만약 원소의 종류가 같아도 순서가 다르다면 다른 순열이 됩니다.
• 조합 : n개의 원소를 사용해서 순서 관계없이 r개의 배열로 나타냅니다. 순서가 존재하지 않기 때문에 원소의 종류가 같다면 같은 조합이 됩니다.

순열과 조합은 원소의 순서가 다를 때, 그것을 중복으로 치는지 안하는지의 차이라고 할 수 있겠내요.

 

파이썬에서는 이런 조합과 순열을 쉽게됩니다.

순열과 조합은 원소의 순서가 다를 때, 그것을 중복으로 치는지 안하는지의 차이라고 할 수 있겠내요.

 

 

 

파이썬에서는 이런 조합과 순열을 쉽게 만들어주는 외장함수가 존재합니다. 

 

• from itertools import combinations
• from itertools import permutations

 

 

combinations는 조합, permutations는 순열에서 주로 사용되는 함수입니다.

 

이걸 잘 사용하면 굳이 for문을 통해 일일이 비교하며 찾지 않아도 간단하게 찾을 수 있답니다.

 

이 문제는 조합의 문제이니 당연히 combinations를 사용해야겠죠?

 

 

combinations를 사용하는 방법은 아주 간단합니다!

 

 

from itertools import combinations
 
x = [1, 2, 3]
cb = combinations(x, 2)

 

이런식으로 combinations(배열, 뽑을 개수)를 사용해 주면

cb[]에 1, 2, 3을 2개씩 뽑았을 때의 모든 조합이 전부 저장된답니다. 

 

정말 Aewsome하지 않나요?

 

 

하지만 combinations를 사용하지 않고 풀고 싶으신 분들도 계시겠죠?

그래서 둘다 준비했답니다~

 

이 문제에서 유의할 사항은 출력값이 붙어서 나오는 경우가 있다는 것인데요.

그래서 print문에서 사용할 수 있는 end와 sep을 사용해 보겠습니다.

 

• end : 프린트가 끝날때, 뒤에 추가로 붙여준다. 디폴트 값은 '\n'이라서, 이것을 다른 내용으로 바꾸면 1줄로 출력할 수 있다.
• sep : 프린트가 끝날때, 뒤에 추가로 붙여준다. 디폴트 값은 '\n'이라서, 이것을 다른 내용으로 바꾸면 1줄로 출력할 수 있다.

print(cb[i], end = ' ')

print(cb[i], sep= '\n')

 

이렇게 사용하면 반복문 안에서 end가 붙은 데이터는 전부 ' '같이 공백문자가 붙어서 나오고, sep이 붙은 데이터는 전부 개행에서 나온답니다.

 

 

 

 

👾트리스티의 답

 

[이것이 무려 3가지의 기술이 합쳐진 컴--비네이숀!]

import sys
from itertools import combinations
 
n, m = map(int, sys.stdin.readline().split())
 
arr = []
for i in range(1, n + 1) :
    arr.append(i)
 
cb = combinations(arr, m)
 
for i in cb :
    for j in range(m) :
        if j != m - 1:
            print(i[j], end = ' ')
        else :
            print(i[j], sep= '\n')

[컴비네이션을 사용하지 않고 풀어보자!]

import sys
n, m = map(int, sys.stdin.readline().split())
 
def alg(l, w, number) :
    if l == number :
        for i in range(len(cb)) :
            if i != number - 1:
                print(cb[i], end = ' ')
            else :
                print(cb[i], sep= '\n')
        return
    
    for i in range(w, len(arr)) :
        cb[l] = arr[i]
        alg(l + 1, i + 1, number)
 
arr = []
for i in range(1, n + 1) :
    arr.append(i)
cb = [0] * m
alg(0, 0, m)
 

※ 잘못된 정보가 있거나 수정사항이 있다면 댓글로 남겨주세요!