본문 바로가기
Develop/알고리즘

[백준/Python] Silver III #15655 N과 M (6)

by favorcat 2023. 1. 30.
반응형
 

15655번: N과 M (6)

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

www.acmicpc.net

문제

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

  • N개의 자연수 중에서 M개를 고른 수열
  • 고른 수열은 오름차순이어야 한다.

입력

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

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

출력

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

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

풀이

n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
ans = []

def backtracking(depth):
  if depth == m:
    print(" ".join(map(str,ans)))
    return
  for i in range(n):
    if depth == 0 or ans[-1] < a[i]:
      ans.append(a[i])
      backtracking(depth+1)
      ans.pop()

backtracking(0)

N과 M 시리즈의 문제 중 하나
전에 풀었던 문제와 비슷하지만 출력이 다르다.
N과 M (5)번은 자신이 아닌 숫자와 수열을 이루어 중복없이 출력
N과 M (8)번은 자신을 포함하여 수열을 이루어 중복없이 출력
이 문제는 수열의 앞에 오는 숫자보다 큰 숫자가 뒤에 오도록 수열을 이루어 중복없이 출력

자신보다 큰 숫자가 뒤에 오도록 하기 위해서는 N과 M (8)번의 코드에서 조건문에서 부등호만 바꿔주면 된다.
ans[-1] <= a[i]에서 ans[-1] < a[i]로 수정하면 된다

 

N과 M 시리즈

N과 M (5) - 자신을 제외한 나머지 숫자와 수열을 이루어 출력

 

[백준/solved.ac] Silver 3 #15654 N과 M (5)

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

blog.favorcat.dev

N과 M (6) - 선행하는 숫자보다 큰 숫자가 나열되는 수열을 이루어 출력

 

[백준/solved.ac] Silver 3 #15655 N과 M (6)

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

blog.favorcat.dev

N과 M (7) - 입력 받은 숫자가 최대 M번만큼 반복하여 수열을 만들어 출력

 

[백준/solved.ac] Silver 3 #15656 N과 M (7)

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

blog.favorcat.dev

N과 M (8) - 숫자를 중복 포함하여 수열을 이루어 출력

 

[백준/Python] Silver III #15657 N과 M (8)

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

blog.favorcat.dev

N과 M (9)

 

[백준/Python] Silver 2 #15663 N과 M (9)

15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하

blog.favorcat.dev

N과 M (10)

 

[백준/Python] Silver II #15664 N과 M (10)

15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하

blog.favorcat.dev

N과 M (11)

 

[백준/Python] Silver II #15665 N과 M (11)

15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하

blog.favorcat.dev

N과 M (12) - 나열되는 숫자는 중복해서 등장, 선행되는 숫자보다 후행하는 숫자가 같거나 큰 수열을 만들어 출력

 

[백준/solved.ac] Silver 2 #15666 N과 M (12)

15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하

blog.favorcat.dev

 

반응형

Comment