[백준] 15650번 N과 M (2) C++ 풀이

---

알고리즘 분류

• 백트래킹

---

문제 설명

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

---

입력 설명

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

---

출력 설명

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

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

---

예제 입력

3 1

4 2

4 4

---

예제 출력

1
2
3

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

 

1 2 3 4

---

아이디어

1~n까지 벡터에 push 하면서 재귀적으로 들어가다가 만약 벡터의 길이가 m과 같아지면 해당 벡터를 출력하고

리턴하고 맨 마지막 숫자를 하나 pop 하는걸 계속 반복한다.

---

알고리즘

1부터 시작해서 n까지 벡터에 숫자를  push 하는 것을 재귀적으로 반복하다가 벡터의 길이가 m이 되면 출력하고 pop 하는 것을 반복한다.

---

코드

#include <iostream>
#include <vector>
using namespace std;
int n,m;
vector<int> arr;
void back(int start)
{
    if(arr.size() == m)
    {
        for(auto &a: arr)
            cout<<a<<" ";
        cout<<"\n";
        return;
    }
    for(int j=start;j<=n;j++)
    {
        arr.push_back(j);
        back(j+1);
        arr.pop_back();
    }
}
int main()
{
    cin>>n>>m;
    back(1);
    return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/15650

맨 처음 생각했던 것은 비트마스킹으로 푸는 방법이었는데

명료한 풀이법이 생각나지 않아서 포기했다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!