본문 바로가기

■ 알고리즘 문제 풀이/BOJ

[BOJ] 백준 15657. N과 M (8)

▶문제설명

[BOJ] 백준 15657. N과 M (8)

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



▶ 설계


[문제]

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

N개의 자연수는 모두 다른 수이다.

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

 중복되는 수열을 여러 번 출력하면 안된다.


N과 M (5) 문제와 거의 같은 문제입니다.

진하게 표시된 

'같은 수를 여러 번 골라도 된다' 라는 조건과 

'고른 수열은 비내림차순이어야 한다' 라는 조건이 추가되었습니다.


[N과 M (5) 풀이 바로가기]

 : https://it-earth.tistory.com/143


N과 M (5) 문제에서는 나왔던 수를 체크하면서 수가 중복되지 않도록 해주었는데

그 부분을 삭제하고, 고른 수를 담는 벡터의 가장 뒤에 있는 수보다 작거나 같은 숫자만 push_back하도록 구현하면

이 문제의 정답이 된다.



▶ 구현



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
void dfs(const vector<int>& numbers, int m, vector<int>& vt){
    if(vt.size() == m){
        for(int n : vt)
            cout<<n<<" ";
        cout<<"\n";
        return;
    }
 
    for(int i=0; i<numbers.size(); i++){
        if(!vt.empty() && vt.back() > numbers[i]) continue;
 
        vt.push_back(numbers[i]);
        dfs(numbers,m,vt);
        vt.pop_back();
    }
}
 
int main(){
    int n,m;
    vector<int> numbers, vt;
    cin>>n>>m;
    for(int i=0,k; i<n; i++){
        cin>>k;
        numbers.push_back(k);
    }
    sort(numbers.begin(), numbers.end());
    dfs(numbers,m,vt);
    return 0;
}
cs



▶ 결과


'■ 알고리즘 문제 풀이 > BOJ' 카테고리의 다른 글

[BOJ] 백준 15656. N과 M (7)  (0) 2020.05.01
[BOJ] 백준 15655. N과 M (6)  (0) 2020.04.27
[BOJ] 백준 15654. N과 M (5)  (0) 2020.04.27
[BOJ] 백준 15652. N과 M (4)  (0) 2020.04.26
[BOJ] 백준 15651. N과 M (3)  (0) 2020.04.24