[백준] 15652번: N과 M(4) - 1~N으로 M길이의 중복되지 않는 수열 만들기 (조합, 같은 수 여러 번 선택 가능)

✏️ 문제 링크

https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

 

 

✏️ 문제 설명 (더보기 클릭 👆🏻)

문제

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

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

입력

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

출력

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

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

예제 입력 1 

3 1

예제 출력 1 

1 2 3

예제 입력 2 

4 2

예제 출력 2 

1 1 1 2 1 3 1 4 2 2 2 3 2 4 3 3 3 4 4 4

예제 입력 3 

3 3

예제 출력 3 

1 1 1 1 1 2 1 1 3 1 2 2 1 2 3 1 3 3 2 2 2 2 2 3 2 3 3 3 3 3

 

✏️ 문제 풀이

중복되지 않으면서 동일한 숫자를 여러번 선택 가능한 조건을 바탕으로 코드를 작성한다. 

중복되지 않으려면 내가 지나온 숫자를 다시 가지 않는 것이다. 이럴 때에는 인덱스를 설정해서 arr를 설정하는 for문의 시작 index를 설정해주면 된다. 만약 동일한 숫자를 사용하지 않는 경우라면 parameter를 넘길 때 i+1(나의 다음 숫자부터 시작)을 넘겨주고, 동일한 숫자를 사용해도 되는 경우라면 parameter를 넘길 때 나부터 시작해도 되니 i그대로를 넘긴다. 그럼 i부터 시작하고 다음 자릿수에서는 나와 동일한 경우가 출력!

 

✏️ 문제 코드

#include <bits/stdc++.h>

using namespace std;
#define MAX 9
int n, m;
int arr[MAX];

void func(int k, int idx){
    if(k==m){
        for(int i=0; i<k; i++)
            cout<<arr[i]<<" ";
        cout<<"\n";
    }else{
        for(int i=idx; i<=n;i++){
            arr[k]=i;
            func(k+1, i);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    func(0, 1);
    return 0;
}

 

 

 

 ⭐ if feedback and question : comment please⭐