백준 15657_N과 M(8) / Python + 백트래킹

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

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

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

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

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

예제 입력 1 

3 1
4 5 2

예제 출력 1 

2
4
5

예제 입력 2 

4 2
9 8 7 1

예제 출력 2 

1 1
1 7
1 8
1 9
7 7
7 8
7 9
8 8
8 9
9 9

예제 입력 3 

4 4
1231 1232 1233 1234

예제 출력 3 

1231 1231 1231 1231
1231 1231 1231 1232
1231 1231 1231 1233
1231 1231 1231 1234
1231 1231 1232 1232
1231 1231 1232 1233
1231 1231 1232 1234
1231 1231 1233 1233
1231 1231 1233 1234
1231 1231 1234 1234
1231 1232 1232 1232
1231 1232 1232 1233
1231 1232 1232 1234
1231 1232 1233 1233
1231 1232 1233 1234
1231 1232 1234 1234
1231 1233 1233 1233
1231 1233 1233 1234
1231 1233 1234 1234
1231 1234 1234 1234
1232 1232 1232 1232
1232 1232 1232 1233
1232 1232 1232 1234
1232 1232 1233 1233
1232 1232 1233 1234
1232 1232 1234 1234
1232 1233 1233 1233
1232 1233 1233 1234
1232 1233 1234 1234
1232 1234 1234 1234
1233 1233 1233 1233
1233 1233 1233 1234
1233 1233 1234 1234
1233 1234 1234 1234
1234 1234 1234 1234

---

문제를 읽자마자 이거 그냥 중복 포함한 조합 구하면 되는거잖아? 해서 라이브러리 import해서 바로 풀었다. 

근데 코테에서 외부 라이브러리 못쓰는 경우도 있으니까.. 없이 구현하는 법도 찾아보고 추가해야겠다.

from itertools import combinations_with_replacement

n, m = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()

for comb in combinations_with_replacement(nums, m):
  for num in comb:
    print(num, end=' ')
  print()

 

 

 

 

*라이브러리 없이 푸는 법

백트래킹이란?

: 한정 조건을 가진 문제를 풀려는 전략.

문제가 한정 조건을 가진 경우 원소의 순서는 해결방법과 무관.

모든 조합을 시도해서 문제의 해를 찾음. > 백트래킹은 많은 부분 조합들을 배제. 시간 단축

구현

해를 얻을 때까지 모든 가능성을 시도!

"""

DFS(깊이 우선 탐색) 중 오답을 만나면 이전 분기점으로 돌아감.

시도해보지 않은 다른 해결 방법이 있으면 시도. 

해결방법이 더 없으면 더 이전의 분기점으로 돌아감.

"""

import sys
n, m = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))
nums.sort()
arr = [-1 for _ in range(m)]

def backtracking(num, prev):
    if num == m:
        print(" ".join(str(x) for x in arr))
        return
    for i in range(prev, n):
        arr[num] = nums[i]
        backtracking(num + 1, i)

backtracking(0, 0)

어렵다..! 파이썬 짱 라이브러리 짱..!